長方形の地図の上で、S のマスを出て E のマスまで行きたい。 地図の文字は . 空きマス、# 壁、S 出発、E 到着、A・B・C 色の扉、a・b・c スイッチである。 1 分ごとに上下左右に隣り合うマス一つへ移る。 地図の外、壁、閉じた扉には移れず、その場にとどまることもできない。 最初はすべての扉が閉じている。 スイッチのマスに入るたびに、そのスイッチと同じ色の扉がすべて一斉に反転する（a は A、b は B、c は C）。 閉じていた扉は開き、開いていた扉は閉じる。 スイッチのマスから出るときは何も起こらない。 同じスイッチにまた入るとまた反転する。 同じ色のスイッチが複数あることもあり、どれに入っても同じように反転する。 反転はスイッチのマスに入るときだけ起こるので、扉のマスに立っている間にその扉が閉じることはない。 S と E は空きマスのように通れ、S のマスにまた入ってもよい。 E に初めて着く最短の時間（分）を出力せよ。 着けなければ -1 を出力せよ。 一行目に R と C、続く R 行に C 文字ずつ地図が与えられる。
入力
1 ≤ R, C ≤ 30。 地図には S と E が一つずつあり、ほかの文字は .#ABCabc だけである。
出力
最短の時間、または -1
例 1 · stdin
2 5
SaaAE
...##
stdout
6
例 2 · stdin
1 5
SaaAE
stdout
6
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
同じマスでも開いている扉が違えば別の状況なので、状態を（マス、開いている扉の色のビットマスク 0～7）にして幅優先探索をします。 状態は多くても 30 × 30 × 8 = 7,200 個です。 スイッチを踏んだら mask ^ (1 << 色)（XOR）でそのビットだけ反転します。 キュー：Python collections.deque、JS・TS は配列に入れて読む位置 head を進める（shift() は毎回先頭を詰めるので遅い）、Java ArrayDeque、C# Queue<int>、C は固定配列と head・tail、C++ std::queue。 Craykon にはビット演算がないので、色ごとに 1・2・4 を足した数で持ち、数学.商(mask, 2) % 2 のように商と余りで読み、立っていれば引き、立っていなければ足して反転します。 キューはリストと head です。 演算子の優先順位も言語ごとに違います：Python は & が == より先なので m >> k & 1 == 0 が意図どおりになりますが、C・C++・JS は == が先なので m >> k & (1 == 0)、つまり常に 0 になり、Java・C# は int と bool を & できずコンパイルエラーになります。 括弧 ((m >> k) & 1) == 0 を書きましょう。 落とし穴は四つ：① 鍵の問題のように mask | bit で一度開けた扉を開けっぱなしにすると、もう一度踏んで閉じた扉を通ってしまいます。 ② 訪問済みの印をマスごとに一つしか持たないと、扉の状態を変えるために同じマスへ戻る道（例）を見落とします。 ③ 上の C の優先順位の間違いで、扉がいつも開いているように見えます。 ④ スイッチを踏んだときに一つの地図を直接書き換えると（扉の文字を . に）、キューにある別の状態までその扉が開いた地図を見てしまいます。 扉の状態は地図ではなく状態の中に持たせます。
Pythonmain.py · 42 行
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);