On a rectangular map you want to leave cell S and reach cell E.
The map characters are . empty, # wall, S start, E exit, A, B, C colored doors, and a, b, c switches.
Every minute you move to one cell adjacent up, down, left or right. You cannot move off the map, into a wall or into a closed door, and you cannot stay in place.
At first every door is closed.
Each time you step onto a switch cell, all doors of that switch's color flip at once (a is A, b is B, c is C). Closed doors open and open doors close.
Nothing happens when you leave a switch cell. Stepping onto the same switch again flips them again.
There may be several switches of the same color, and stepping onto any of them flips the same way.
Flips happen only when you step onto a switch cell, so a door never closes while you stand on it.
S and E can be passed like empty cells, and you may step onto S again.
Print the shortest time (in minutes) to first reach E. If it cannot be reached, print -1.
The first line gives R and C, and the next R lines give the map, C characters each.
Input
1 ≤ R, C ≤ 30. The map has exactly one S and one E, and the other characters are only .#ABCabc.
Output
The shortest time, or -1
Example 1 · stdin
2 5
SaaAE
...##
stdout
6
Example 2 · stdin
1 5
SaaAE
stdout
6
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The same cell with different doors open is a different situation, so take the state as (cell, bitmask 0–7 of open door colors) and run a breadth-first search. There are at most 30 × 30 × 8 = 7,200 states. Stepping onto a switch flips just that bit with mask ^ (1 << color) (XOR). Queues: Python collections.deque, JS/TS an array plus a read position head (shift() moves the front every time and is slow), Java ArrayDeque, C# Queue<int>, C a fixed array with head and tail, C++ std::queue. Craykon has no bit operators, so it stores the colors as a sum of 1, 2 and 4, reads a bit with quotient and remainder as in Mathf.Quot(mask, 2) % 2, and flips by subtracting when on and adding when off; its queue is a list plus head. Operator precedence also differs: in Python & comes before ==, so m >> k & 1 == 0 means what you want, but in C, C++ and JS == comes first, giving m >> k & (1 == 0), which is always 0, and in Java and C# you cannot & an int with a bool, so it is a compile error. Write the parentheses ((m >> k) & 1) == 0. Four traps: (1) Treating switches like keys with mask | bit keeps a door open forever, so you walk through a door that stepping again had closed. (2) Keeping only one visited mark per cell misses paths that must come back to the same cell to change the doors (the example). (3) The C precedence slip above makes every door look open. (4) Editing the one shared map when stepping on a switch (turning door letters into .) makes the other states in the queue see that door open too. The door state belongs in the search state, not in the map.
Pythonmain.py · 42 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
// 크레이콘에는 비트 연산이 없어서, 열린 문 색 세 개를 0~7의 수(1·2·4의 합)로 담고 몫과 나머지로 읽는다첫줄 = Console.ReadNumbers();r = 첫줄[0];c = 첫줄[1];grid = [];start = 0;for (y = 0; y < r; y++){ 줄 = Console.ReadLine().Trim(); grid.Add(줄); for (x = 0; x < c; x++) { if (줄[x] == "S") { start = y * c + x; } }}문색 = Dict(); // 문 글자 → 그 색의 값(1, 2, 4)문색["A"] = 1;문색["B"] = 2;문색["C"] = 4;스위치색 = Dict();스위치색["a"] = 1;스위치색["b"] = 2;스위치색["c"] = 4;// 상태 번호 = 칸 * 8 + 열린 문 색의 합dist = NewList(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;while (head < queue.Count && answer < 0){ s = queue[head]; head++; cell = Mathf.Quot(s, 8); mask = s % 8; y = Mathf.Quot(cell, c); x = cell % c; for (k = 0; k < 4; k++) { ny = y + DY[k]; nx = x + DX[k]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) { continue; } ch = grid[ny][nx]; if (ch == "#") { continue; } if (문색.Contains(ch) && Mathf.Quot(mask, 문색[ch]) % 2 == 0) { continue; // 닫힌 문 } nmask = mask; if (스위치색.Contains(ch)) { v = 스위치색[ch]; // 들어설 때마다 뒤집는다: 켜져 있으면 빼고, 꺼져 있으면 더한다 if (Mathf.Quot(mask, v) % 2 == 1) { nmask = mask - v; } else { nmask = mask + v; } } if (ch == "E") { answer = dist[s] + 1; break; } ns = (ny * c + nx) * 8 + nmask; if (dist[ns] < 0) { dist[ns] = dist[s] + 1; queue.Add(ns); } }}Console.WriteLine(answer);