import sysfrom collections import dequedef main(): data = sys.stdin.read().split() r, c = int(data[0]), int(data[1]) grid = data[2:2 + r] for y in range(r): for x in range(c): if grid[y][x] == "S": start = (y, x) # 상태 = (칸, 열린 문 색의 비트마스크). 같은 칸이라도 열린 문이 다르면 다른 상태다 dist = [[[-1] * 8 for _ in range(c)] for _ in range(r)] sy, sx = start dist[sy][sx][0] = 0 queue = deque([(sy, sx, 0)]) while queue: y, x, mask = queue.popleft() d = dist[y][x][mask] for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)): ny, nx = y + dy, x + dx if not (0 <= ny < r and 0 <= nx < c): continue ch = grid[ny][nx] if ch == "#": continue if ch in "ABC" and not mask >> (ord(ch) - ord("A")) & 1: continue # 닫힌 문 nmask = mask if ch in "abc": nmask = mask ^ (1 << (ord(ch) - ord("a"))) # 들어설 때마다 뒤집는다 if ch == "E": print(d + 1) return if dist[ny][nx][nmask] < 0: dist[ny][nx][nmask] = d + 1 queue.append((ny, nx, nmask)) print(-1)main()
JavaScriptmain.js · 40 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const r = Number(data[0]);const c = Number(data[1]);const grid = data.slice(2, 2 + r);let start = 0;for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "S") start = y * c + x;// 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크const dist = new Array(r * c * 8).fill(-1);const queue = [start * 8];dist[start * 8] = 0;const DY = [-1, 1, 0, 0];const DX = [0, 0, -1, 1];let answer = -1;search: for (let head = 0; head < queue.length; head++) { const s = queue[head]; const cell = s >> 3; const mask = s & 7; const y = Math.floor(cell / c); const x = cell % c; for (let k = 0; k < 4; k++) { const ny = y + DY[k]; const nx = x + DX[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; const ch = grid[ny][nx]; if (ch === "#") continue; if (ch >= "A" && ch <= "C" && ((mask >> (ch.charCodeAt(0) - 65)) & 1) === 0) continue; // 닫힌 문 let nmask = mask; if (ch >= "a" && ch <= "c") nmask ^= 1 << (ch.charCodeAt(0) - 97); // 들어설 때마다 뒤집는다 if (ch === "E") { answer = dist[s] + 1; break search; } const ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue.push(ns); } }}console.log(answer);
TypeScriptmain.ts · 40 行
const data: string[] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const r = Number(data[0]);const c = Number(data[1]);const grid = data.slice(2, 2 + r);let start = 0;for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "S") start = y * c + x;// 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크const dist: number[] = new Array(r * c * 8).fill(-1);const queue: number[] = [start * 8];dist[start * 8] = 0;const DY = [-1, 1, 0, 0];const DX = [0, 0, -1, 1];let answer = -1;search: for (let head = 0; head < queue.length; head++) { const s = queue[head]; const cell = s >> 3; const mask = s & 7; const y = Math.floor(cell / c); const x = cell % c; for (let k = 0; k < 4; k++) { const ny = y + DY[k]; const nx = x + DX[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; const ch = grid[ny][nx]; if (ch === "#") continue; if (ch >= "A" && ch <= "C" && ((mask >> (ch.charCodeAt(0) - 65)) & 1) === 0) continue; // 닫힌 문 let nmask = mask; if (ch >= "a" && ch <= "c") nmask ^= 1 << (ch.charCodeAt(0) - 97); // 들어설 때마다 뒤집는다 if (ch === "E") { answer = dist[s] + 1; break search; } const ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue.push(ns); } }}console.log(answer);
JavaMain.java · 48 行
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int r = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken()); char[][] grid = new char[r][]; int start = 0; for (int y = 0; y < r; y++) { grid[y] = br.readLine().trim().toCharArray(); for (int x = 0; x < c; x++) if (grid[y][x] == 'S') start = y * c + x; } // 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크 int[] dist = new int[r * c * 8]; Arrays.fill(dist, -1); ArrayDeque<Integer> queue = new ArrayDeque<>(); dist[start * 8] = 0; queue.add(start * 8); int[] dy = {-1, 1, 0, 0}, dx = {0, 0, -1, 1}; while (!queue.isEmpty()) { int s = queue.poll(); int cell = s / 8, mask = s % 8; int y = cell / c, x = cell % c; for (int k = 0; k < 4; k++) { int ny = y + dy[k], nx = x + dx[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; char ch = grid[ny][nx]; if (ch == '#') continue; if (ch >= 'A' && ch <= 'C' && ((mask >> (ch - 'A')) & 1) == 0) continue; // 닫힌 문 int nmask = mask; if (ch >= 'a' && ch <= 'c') nmask ^= 1 << (ch - 'a'); // 들어설 때마다 뒤집는다 if (ch == 'E') { System.out.println(dist[s] + 1); return; } int ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue.add(ns); } } } System.out.println(-1); }}
C#Main.cs · 53 行
using System;using System.Collections.Generic;class Program{ static void Main() { var first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int r = int.Parse(first[0]), c = int.Parse(first[1]); var grid = new string[r]; int start = 0; for (int y = 0; y < r; y++) { grid[y] = Console.ReadLine().Trim(); for (int x = 0; x < c; x++) if (grid[y][x] == 'S') start = y * c + x; } // 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크 var dist = new int[r * c * 8]; Array.Fill(dist, -1); var queue = new Queue<int>(); dist[start * 8] = 0; queue.Enqueue(start * 8); int[] dy = { -1, 1, 0, 0 }, dx = { 0, 0, -1, 1 }; while (queue.Count > 0) { int s = queue.Dequeue(); int cell = s / 8, mask = s % 8; int y = cell / c, x = cell % c; for (int k = 0; k < 4; k++) { int ny = y + dy[k], nx = x + dx[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; char ch = grid[ny][nx]; if (ch == '#') continue; if (ch >= 'A' && ch <= 'C' && ((mask >> (ch - 'A')) & 1) == 0) continue; // 닫힌 문 int nmask = mask; if (ch >= 'a' && ch <= 'c') nmask ^= 1 << (ch - 'a'); // 들어설 때마다 뒤집는다 if (ch == 'E') { Console.WriteLine(dist[s] + 1); return; } int ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue.Enqueue(ns); } } } Console.WriteLine(-1); }}
C++main.cpp · 48 行
#include <iostream>#include <queue>#include <string>#include <vector>int main() { int r, c; std::cin >> r >> c; std::vector<std::string> grid(r); int start = 0; for (int y = 0; y < r; y++) { std::cin >> grid[y]; for (int x = 0; x < c; x++) if (grid[y][x] == 'S') start = y * c + x; } // 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크 std::vector<int> dist(r * c * 8, -1); std::queue<int> q; dist[start * 8] = 0; q.push(start * 8); const int dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1}; while (!q.empty()) { int s = q.front(); q.pop(); int cell = s / 8, mask = s % 8; int y = cell / c, x = cell % c; for (int k = 0; k < 4; k++) { int ny = y + dy[k], nx = x + dx[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; char ch = grid[ny][nx]; if (ch == '#') continue; if (ch >= 'A' && ch <= 'C' && ((mask >> (ch - 'A')) & 1) == 0) continue; // 닫힌 문 int nmask = mask; if (ch >= 'a' && ch <= 'c') nmask ^= 1 << (ch - 'a'); // 들어설 때마다 뒤집는다 if (ch == 'E') { std::cout << dist[s] + 1 << '\n'; return 0; } int ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; q.push(ns); } } } std::cout << -1 << '\n'; return 0;}
Cmain.c · 46 行
#include <stdio.h>static char grid[30][32];static int dist[30 * 30 * 8];static int queue[30 * 30 * 8]; /* 상태마다 많아야 한 번 들어간다 */int main(void) { int r, c, start = 0; scanf("%d %d", &r, &c); for (int y = 0; y < r; y++) { scanf("%31s", grid[y]); for (int x = 0; x < c; x++) if (grid[y][x] == 'S') start = y * c + x; } /* 상태 번호 = 칸 * 8 + 열린 문 색의 비트마스크 */ for (int i = 0; i < r * c * 8; i++) dist[i] = -1; int head = 0, tail = 0; dist[start * 8] = 0; queue[tail++] = start * 8; const int dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1}; while (head < tail) { int s = queue[head++]; int cell = s / 8, mask = s % 8; int y = cell / c, x = cell % c; for (int k = 0; k < 4; k++) { int ny = y + dy[k], nx = x + dx[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; char ch = grid[ny][nx]; if (ch == '#') continue; if (ch >= 'A' && ch <= 'C' && ((mask >> (ch - 'A')) & 1) == 0) continue; /* 닫힌 문 */ int nmask = mask; if (ch >= 'a' && ch <= 'c') nmask ^= 1 << (ch - 'a'); /* 들어설 때마다 뒤집는다 */ if (ch == 'E') { printf("%d\n", dist[s] + 1); return 0; } int ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue[tail++] = ns; } } } printf("-1\n"); return 0;}
Craykonmain.cray · 88 行
// 크레이콘에는 비트 연산이 없어서, 열린 문 색 세 개를 0~7의 수(1·2·4의 합)로 담고 몫과 나머지로 읽는다첫줄 = 控制台.读数字();r = 첫줄[0];c = 첫줄[1];grid = [];start = 0;循环 (y = 0; y < r; y++){ 줄 = 控制台.读行().去空白(); grid.添加(줄); 循环 (x = 0; x < c; x++) { 如果 (줄[x] == "S") { start = y * c + x; } }}문색 = 字典(); // 문 글자 → 그 색의 값(1, 2, 4)문색["A"] = 1;문색["B"] = 2;문색["C"] = 4;스위치색 = 字典();스위치색["a"] = 1;스위치색["b"] = 2;스위치색["c"] = 4;// 상태 번호 = 칸 * 8 + 열린 문 색의 합dist = 新列表(r * c * 8, -1);queue = [start * 8];dist[start * 8] = 0;DY = [-1, 1, 0, 0];DX = [0, 0, -1, 1];answer = -1;head = 0;当 (head < queue.数量 && answer < 0){ s = queue[head]; head++; cell = 数学.商(s, 8); mask = s % 8; y = 数学.商(cell, c); x = cell % c; 循环 (k = 0; k < 4; k++) { ny = y + DY[k]; nx = x + DX[k]; 如果 (ny < 0 || ny >= r || nx < 0 || nx >= c) { 继续; } ch = grid[ny][nx]; 如果 (ch == "#") { 继续; } 如果 (문색.包含(ch) && 数学.商(mask, 문색[ch]) % 2 == 0) { 继续; // 닫힌 문 } nmask = mask; 如果 (스위치색.包含(ch)) { v = 스위치색[ch]; // 들어설 때마다 뒤집는다: 켜져 있으면 빼고, 꺼져 있으면 더한다 如果 (数学.商(mask, v) % 2 == 1) { nmask = mask - v; } 否则 { nmask = mask + v; } } 如果 (ch == "E") { answer = dist[s] + 1; 跳出; } ns = (ny * c + nx) * 8 + nmask; 如果 (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue.添加(ns); } }}控制台.输出(answer);