R 行 C 列の洞窟の地図が与えられる。 '.' は空きマス、'#' は岩、'S' は探検家が最初に立っている空きマス、英小文字はその文字の鍵が置かれた空きマス、'S' を除く英大文字は扉である。 大文字の扉は、同じ文字の小文字の鍵をすでに持っているときだけ入れる（例：'B' の扉には 'b' の鍵が必要）。 鍵はそのマスに初めて入るときに拾い、一度拾った鍵はずっと持っている。 探検家は最初のマスを行ったマスとして印をつけ、次をくり返す。 今のマスから上、右、下、左の順に隣のマスを見て、地図の中で、岩でなく、まだ行っておらず、入れる最初のマスへ一マス動く。 そのマスに行ったマスの印をつける。 そのような隣がなければ、今のマスに初めて入ったときに出てきたマスへ一マス戻る。 戻ったマスでも上からもう一度見る。 最初のマスで行ける隣がなければ探検を終える。 前に進むのも戻るのも一回の移動と数える。 一行目に移動の回数 T と行ったマスの数（最初のマスを含む）を空白区切りで出力せよ。 二行目に新しく拾った鍵の文字を拾った順につなげて出力せよ（すでに持っている文字の鍵をまた拾ったものは書かない）。 一つもなければ '-' を出力する。 続いて質問 t ごとに、t 回動いた直後に探検家がいるマスの行番号と列番号（左上が 1 1）を一行に出力せよ。 0 回動いた直後は最初のマスで、t が T より大きければ探検を終えたマス（最初のマス）である。
入力
一行目に R と C、続く R 行に長さ C の地図の文字列、次の行に質問の数 Q、次の行に質問 t が Q 個、空白区切りで与えられる。 1 ≤ R, C ≤ 50、'S' はちょうど一つ、1 ≤ Q ≤ 100、0 ≤ t ≤ 10,000。
出力
一行目に T と行ったマスの数、二行目に拾った鍵の文字または '-'、続く Q 行に各行 '行 列'
例 1 · stdin
3 4
S.A.
.#b#
a...
4
0 3 10 100
stdout
18 10
ab
1 1
2 1
1 3
1 1
例 2 · stdin
3 3
#A#
#Sa
###
6
0 1 2 3 4 5
stdout
4 3
a
2 2
2 3
2 2
1 2
2 2
2 2
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
壁を手さぐりし、ふさがれたら戻る探検は深さ優先探索（DFS）で、「これまで入ってきた道」をスタックで持ち歩けばよいです：進んだら入れ（push）、ふさがれたら取り出して（pop）新しいいちばん上のマスへ戻ります。 スタックに最初のマスだけが残って行くところがなければ終わりです。 いちばん多い罠は、ふつうの再帰 DFS（for で方向ごとに再帰呼び出し）をそのまま使うことです：戻ったあと次の方向から続けて見るので、その間に拾った鍵で開いた前の方向の扉をもう見ません（例 2 では上の 'A' の扉をずっと開けられず T が 2 になります）。 この問題はマスに立つたびに上からもう一度見ると決めているので、スタックのいちばん上のマスで毎回四方向を最初から見ればよいです（行った印があるので、一つのマスで見直すのは多くても四方向ずつで速いです）。 二つ目の罠は深さです：何もない 50×50 の洞窟では道が 2,500 マスまで深くなり、再帰で解くと Python の既定の再帰上限（1,000）を超え、Craykon も数千段で止まることがあります — だから自分で作るスタックが安全です。 ほかに：戻る歩みも移動として数える、t が T より大きいときは最初のマスで答える（配列の終わりを越えて読まない）、行・列の番号は 1 から。 言語ごとに：Python はリスト append/pop と for … else（break せずに終わると else）、Java は ArrayDeque<int[]> の push/pop/peek、C# は Stack<(int y, int x)> と Array.FindIndex、HashSet.Add は新しく入れたときだけ true なので鍵を初めて拾ったかがすぐわかります。 C++ は std::vector をスタックに（push_back/pop_back/back）と std::find_if、C はマス番号の配列といちばん上の位置の変数、JavaScript・TypeScript は配列 push/pop と STEPS.find(…)（なければ undefined）。 Craykon はマスを一つの数 y * c + x に広げてリスト path に 追加/位置で取り除く(個数 - 1) し、扉の鍵は ch.小文字() で探します。 Craykon のリストの範囲外読み取りは実行エラーなので、数学.小さい方(t, moves) で端を押さえます。
Pythonmain.py · 54 行
import sysdata = sys.stdin.read().split("\n")r, c = map(int, data[0].split())grid = [data[1 + y].strip() for y in range(r)]q = int(data[1 + r])queries = list(map(int, data[2 + r].split()))STEPS = ((-1, 0), (0, 1), (1, 0), (0, -1)) # 위, 오른쪽, 아래, 왼쪽start = next((y, x) for y in range(r) for x in range(c) if grid[y][x] == "S")visited = [[False] * c for _ in range(r)]visited[start[0]][start[1]] = Truekeys = set()picked = [] # 새로 얻은 열쇠(얻은 차례)path = [start] # 지금까지 들어온 길(스택): 맨 위가 지금 자리log = [start] # log[t] = t번 움직인 뒤의 자리def can_enter(y, x): if not (0 <= y < r and 0 <= x < c) or visited[y][x]: return False ch = grid[y][x] if ch == "#": return False if ch.isupper(): return ch.lower() in keys # 문은 맞는 열쇠가 있어야 들어간다 return Truewhile True: y, x = path[-1] # 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 for dy, dx in STEPS: ny, nx = y + dy, x + dx if can_enter(ny, nx): visited[ny][nx] = True ch = grid[ny][nx] if ch.islower() and ch not in keys: keys.add(ch) picked.append(ch) path.append((ny, nx)) break else: if len(path) == 1: break # 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.pop() # 왔던 칸으로 한 칸 되돌아간다 log.append(path[-1])moves = len(log) - 1out = [f"{moves} {sum(map(sum, visited))}", "".join(picked) or "-"]for t in queries: y, x = log[min(t, moves)] # 멈춘 뒤에는 처음 자리에 그대로 있다 out.append(f"{y + 1} {x + 1}")print("\n".join(out))
JavaScriptmain.js · 54 行
const data = require("fs").readFileSync(0, "utf8").split("\n");const [r, c] = data[0].trim().split(/\s+/).map(Number);const grid = [];for (let y = 0; y < r; y++) grid.push(data[1 + y].trim());const queries = data[2 + r].trim().split(/\s+/).map(Number);const STEPS = [[-1, 0], [0, 1], [1, 0], [0, -1]]; // 위, 오른쪽, 아래, 왼쪽let start = null;for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "S") start = [y, x];const visited = Array.from({ length: r }, () => new Array(c).fill(false));visited[start[0]][start[1]] = true;const keys = new Set();let picked = ""; // 새로 얻은 열쇠(얻은 차례)const path = [start]; // 지금까지 들어온 길(스택): 맨 끝이 지금 자리const log = [start]; // log[t] = t번 움직인 뒤의 자리const isUpper = (ch) => ch >= "A" && ch <= "Z";const isLower = (ch) => ch >= "a" && ch <= "z";function canEnter(y, x) { if (y < 0 || y >= r || x < 0 || x >= c || visited[y][x]) return false; const ch = grid[y][x]; if (ch === "#") return false; if (isUpper(ch)) return keys.has(ch.toLowerCase()); // 문은 맞는 열쇠가 있어야 들어간다 return true;}while (true) { const [y, x] = path[path.length - 1]; // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 const step = STEPS.find(([dy, dx]) => canEnter(y + dy, x + dx)); if (step !== undefined) { const ny = y + step[0], nx = x + step[1]; visited[ny][nx] = true; const ch = grid[ny][nx]; if (isLower(ch) && !keys.has(ch)) { keys.add(ch); picked += ch; } path.push([ny, nx]); } else { if (path.length === 1) break; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.pop(); // 왔던 칸으로 한 칸 되돌아간다 } log.push(path[path.length - 1]);}const moves = log.length - 1;const seen = visited.flat().filter(Boolean).length;const out = [`${moves} ${seen}`, picked || "-"];for (const t of queries) { const [y, x] = log[Math.min(t, moves)]; // 멈춘 뒤에는 처음 자리에 그대로 있다 out.push(`${y + 1} ${x + 1}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 57 行
import { readFileSync } from "node:fs";type Cell = [number, number];const data: string[] = readFileSync(0, "utf8").split("\n");const [r, c] = data[0].trim().split(/\s+/).map(Number);const grid: string[] = [];for (let y = 0; y < r; y++) grid.push(data[1 + y].trim());const queries = data[2 + r].trim().split(/\s+/).map(Number);const STEPS: Cell[] = [[-1, 0], [0, 1], [1, 0], [0, -1]]; // 위, 오른쪽, 아래, 왼쪽let start: Cell = [0, 0];for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "S") start = [y, x];const visited: boolean[][] = Array.from({ length: r }, () => new Array<boolean>(c).fill(false));visited[start[0]][start[1]] = true;const keys = new Set<string>();let picked = ""; // 새로 얻은 열쇠(얻은 차례)const path: Cell[] = [start]; // 지금까지 들어온 길(스택): 맨 끝이 지금 자리const log: Cell[] = [start]; // log[t] = t번 움직인 뒤의 자리const isUpper = (ch: string): boolean => ch >= "A" && ch <= "Z";const isLower = (ch: string): boolean => ch >= "a" && ch <= "z";function canEnter(y: number, x: number): boolean { if (y < 0 || y >= r || x < 0 || x >= c || visited[y][x]) return false; const ch = grid[y][x]; if (ch === "#") return false; if (isUpper(ch)) return keys.has(ch.toLowerCase()); // 문은 맞는 열쇠가 있어야 들어간다 return true;}while (true) { const [y, x] = path[path.length - 1]; // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 const step = STEPS.find(([dy, dx]) => canEnter(y + dy, x + dx)); if (step !== undefined) { const ny = y + step[0], nx = x + step[1]; visited[ny][nx] = true; const ch = grid[ny][nx]; if (isLower(ch) && !keys.has(ch)) { keys.add(ch); picked += ch; } path.push([ny, nx]); } else { if (path.length === 1) break; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.pop(); // 왔던 칸으로 한 칸 되돌아간다 } log.push(path[path.length - 1]);}const moves = log.length - 1;const seen = visited.flat().filter(Boolean).length;const out = [`${moves} ${seen}`, picked || "-"];for (const t of queries) { const [y, x] = log[Math.min(t, moves)]; // 멈춘 뒤에는 처음 자리에 그대로 있다 out.push(`${y + 1} ${x + 1}`);}console.log(out.join("\n"));
JavaMain.java · 79 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;public class Main { static int r, c; static char[][] grid; static boolean[][] visited; static boolean[] keys = new boolean[26]; static boolean canEnter(int y, int x) { if (y < 0 || y >= r || x < 0 || x >= c || visited[y][x]) return false; char ch = grid[y][x]; if (ch == '#') return false; if (Character.isUpperCase(ch)) return keys[ch - 'A']; // 문은 맞는 열쇠가 있어야 들어간다 return true; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); r = Integer.parseInt(st.nextToken()); c = Integer.parseInt(st.nextToken()); grid = new char[r][]; int sy = 0, sx = 0; for (int y = 0; y < r; y++) { grid[y] = in.readLine().trim().toCharArray(); for (int x = 0; x < c; x++) if (grid[y][x] == 'S') { sy = y; sx = x; } } int q = Integer.parseInt(in.readLine().trim()); st = new StringTokenizer(in.readLine()); int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1}; // 위, 오른쪽, 아래, 왼쪽 visited = new boolean[r][c]; visited[sy][sx] = true; StringBuilder picked = new StringBuilder(); // 새로 얻은 열쇠(얻은 차례) ArrayDeque<int[]> path = new ArrayDeque<>(); // 지금까지 들어온 길(스택): 맨 위가 지금 자리 path.push(new int[] {sy, sx}); List<int[]> log = new ArrayList<>(); // log.get(t) = t번 움직인 뒤의 자리 log.add(path.peek()); int seen = 1; while (true) { int[] cur = path.peek(); // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 int d = 0; while (d < 4 && !canEnter(cur[0] + dy[d], cur[1] + dx[d])) d++; if (d < 4) { int ny = cur[0] + dy[d], nx = cur[1] + dx[d]; visited[ny][nx] = true; seen++; char ch = grid[ny][nx]; if (Character.isLowerCase(ch) && !keys[ch - 'a']) { keys[ch - 'a'] = true; picked.append(ch); } path.push(new int[] {ny, nx}); } else { if (path.size() == 1) break; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.pop(); // 왔던 칸으로 한 칸 되돌아간다 } log.add(path.peek()); } int moves = log.size() - 1; StringBuilder out = new StringBuilder(); out.append(moves).append(' ').append(seen).append('\n'); out.append(picked.length() > 0 ? picked : "-").append('\n'); for (int i = 0; i < q; i++) { int[] at = log.get(Math.min(Integer.parseInt(st.nextToken()), moves)); // 멈춘 뒤에는 처음 자리에 그대로 있다 out.append(at[0] + 1).append(' ').append(at[1] + 1).append('\n'); } System.out.print(out); }}
C#Main.cs · 75 行
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static void Main() { int[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int r = first[0], c = first[1]; var grid = new string[r]; (int y, int x) start = (0, 0); for (int y = 0; y < r; y++) { grid[y] = Console.ReadLine().Trim(); int x = grid[y].IndexOf('S'); if (x >= 0) start = (y, x); } int q = int.Parse(Console.ReadLine().Trim()); int[] queries = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); (int dy, int dx)[] steps = { (-1, 0), (0, 1), (1, 0), (0, -1) }; // 위, 오른쪽, 아래, 왼쪽 var visited = new bool[r, c]; visited[start.y, start.x] = true; var keys = new HashSet<char>(); var picked = new StringBuilder(); // 새로 얻은 열쇠(얻은 차례) var path = new Stack<(int y, int x)>(); // 지금까지 들어온 길(스택): 맨 위가 지금 자리 path.Push(start); var log = new List<(int y, int x)> { start }; // log[t] = t번 움직인 뒤의 자리 int seen = 1; bool CanEnter(int y, int x) { if (y < 0 || y >= r || x < 0 || x >= c || visited[y, x]) return false; char ch = grid[y][x]; if (ch == '#') return false; if (char.IsUpper(ch)) return keys.Contains(char.ToLower(ch)); // 문은 맞는 열쇠가 있어야 들어간다 return true; } while (true) { var (y, x) = path.Peek(); // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 int d = Array.FindIndex(steps, s => CanEnter(y + s.dy, x + s.dx)); if (d >= 0) { int ny = y + steps[d].dy, nx = x + steps[d].dx; visited[ny, nx] = true; seen++; char ch = grid[ny][nx]; if (char.IsLower(ch) && keys.Add(ch)) picked.Append(ch); // Add는 새로 넣었을 때만 true path.Push((ny, nx)); } else { if (path.Count == 1) break; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.Pop(); // 왔던 칸으로 한 칸 되돌아간다 } log.Add(path.Peek()); } int moves = log.Count - 1; var out_ = new StringBuilder(); out_.Append(moves).Append(' ').Append(seen).Append('\n'); out_.Append(picked.Length > 0 ? picked.ToString() : "-").Append('\n'); foreach (int t in queries) { var (y, x) = log[Math.Min(t, moves)]; // 멈춘 뒤에는 처음 자리에 그대로 있다 out_.Append(y + 1).Append(' ').Append(x + 1).Append('\n'); } Console.Write(out_); }}
C++main.cpp · 66 行
#include <algorithm>#include <array>#include <cctype>#include <iostream>#include <string>#include <utility>#include <vector>int main() { int r, c; std::cin >> r >> c; std::vector<std::string> grid(r); std::pair<int, int> start{0, 0}; for (int y = 0; y < r; y++) { std::cin >> grid[y]; if (auto x = grid[y].find('S'); x != std::string::npos) start = {y, static_cast<int>(x)}; } const std::array<std::pair<int, int>, 4> STEPS{{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}}; // 위, 오른쪽, 아래, 왼쪽 std::vector<std::vector<bool>> visited(r, std::vector<bool>(c, false)); std::array<bool, 26> keys{}; std::string picked; // 새로 얻은 열쇠(얻은 차례) std::vector<std::pair<int, int>> path{start}; // 지금까지 들어온 길(스택): 맨 끝이 지금 자리 std::vector<std::pair<int, int>> log{start}; // log[t] = t번 움직인 뒤의 자리 visited[start.first][start.second] = true; int seen = 1; auto canEnter = [&](int y, int x) { if (y < 0 || y >= r || x < 0 || x >= c || visited[y][x]) return false; char ch = grid[y][x]; if (ch == '#') return false; if (std::isupper(static_cast<unsigned char>(ch))) return keys[ch - 'A']; // 문은 맞는 열쇠가 있어야 들어간다 return true; }; while (true) { auto [y, x] = path.back(); // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 auto it = std::find_if(STEPS.begin(), STEPS.end(), [&](const auto& s) { return canEnter(y + s.first, x + s.second); }); if (it != STEPS.end()) { int ny = y + it->first, nx = x + it->second; visited[ny][nx] = true; seen++; char ch = grid[ny][nx]; if (std::islower(static_cast<unsigned char>(ch)) && !keys[ch - 'a']) { keys[ch - 'a'] = true; picked += ch; } path.emplace_back(ny, nx); } else { if (path.size() == 1) break; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.pop_back(); // 왔던 칸으로 한 칸 되돌아간다 } log.push_back(path.back()); } int moves = static_cast<int>(log.size()) - 1; std::cout << moves << " " << seen << "\n" << (picked.empty() ? "-" : picked) << "\n"; int q; std::cin >> q; for (int i = 0; i < q; i++) { int t; std::cin >> t; auto [y, x] = log[std::min(t, moves)]; // 멈춘 뒤에는 처음 자리에 그대로 있다 std::cout << y + 1 << " " << x + 1 << "\n"; }}
Cmain.c · 66 行
#include <ctype.h>#include <stdio.h>#define MAXN 50static char grid[MAXN][MAXN + 2];static int visited[MAXN][MAXN];static int keys[26];static int r, c;static int path[MAXN * MAXN]; /* 지금까지 들어온 길(스택): 칸 번호 y * c + x */static int logCell[2 * MAXN * MAXN]; /* logCell[t] = t번 움직인 뒤의 자리 */static int canEnter(int y, int x) { if (y < 0 || y >= r || x < 0 || x >= c || visited[y][x]) return 0; char ch = grid[y][x]; if (ch == '#') return 0; if (isupper((unsigned char)ch)) return keys[ch - 'A']; /* 문은 맞는 열쇠가 있어야 들어간다 */ return 1;}int main(void) { int q, start = 0; scanf("%d %d", &r, &c); for (int y = 0; y < r; y++) { scanf("%51s", grid[y]); for (int x = 0; x < c; x++) if (grid[y][x] == 'S') start = y * c + x; } const int DY[4] = {-1, 0, 1, 0}, DX[4] = {0, 1, 0, -1}; /* 위, 오른쪽, 아래, 왼쪽 */ char picked[27]; int npicked = 0, top = 0, moves = 0, seen = 1; visited[start / c][start % c] = 1; path[top++] = start; logCell[0] = start; for (;;) { int y = path[top - 1] / c, x = path[top - 1] % c; /* 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 */ int d = 0; while (d < 4 && !canEnter(y + DY[d], x + DX[d])) d++; if (d < 4) { int ny = y + DY[d], nx = x + DX[d]; visited[ny][nx] = 1; seen++; char ch = grid[ny][nx]; if (islower((unsigned char)ch) && !keys[ch - 'a']) { keys[ch - 'a'] = 1; picked[npicked++] = ch; } path[top++] = ny * c + nx; } else { if (top == 1) break; /* 처음 자리에서 더 갈 곳이 없으면 멈춘다 */ top--; /* 왔던 칸으로 한 칸 되돌아간다 */ } logCell[++moves] = path[top - 1]; } picked[npicked] = '\0'; printf("%d %d\n%s\n", moves, seen, npicked > 0 ? picked : "-"); scanf("%d", &q); for (int i = 0; i < q; i++) { int t; scanf("%d", &t); int at = logCell[t < moves ? t : moves]; /* 멈춘 뒤에는 처음 자리에 그대로 있다 */ printf("%d %d\n", at / c + 1, at % c + 1); } return 0;}
Craykonmain.cray · 104 行
첫줄 = コンソール.数読み();r = 첫줄[0];c = 첫줄[1];grid = [];start = 0; // 칸은 수 하나(y * c + x)로 다룬다繰り返す (y = 0; y < r; y++){ 줄 = コンソール.行読み().空白除去(); grid.追加(줄); x = 줄.位置検索("S"); もし (x >= 0) { start = y * c + x; }}q = コンソール.行読み().空白除去().数に();queries = コンソール.数読み();DY = [-1, 0, 1, 0]; // 위, 오른쪽, 아래, 왼쪽DX = [0, 1, 0, -1];visited = 新リスト(r * c, 偽);visited[start] = 真;keys = 辞書();picked = ""; // 새로 얻은 열쇠(얻은 차례)대문자인가(ch){ 返す ch >= "A" && ch <= "Z";}소문자인가(ch){ 返す ch >= "a" && ch <= "z";}들어갈수있나(y, x){ もし (y < 0 || y >= r || x < 0 || x >= c) { 返す 偽; } もし (visited[y * c + x]) { 返す 偽; } ch = grid[y][x]; もし (ch == "#") { 返す 偽; } もし (대문자인가(ch)) { 返す keys.含む(ch.小文字()); // 문은 맞는 열쇠가 있어야 들어간다 } 返す 真;}path = [start]; // 지금까지 들어온 길(스택): 맨 끝이 지금 자리log = [start]; // log[t] = t번 움직인 뒤의 자리seen = 1;間 (真){ cell = path[path.個数 - 1]; y = 数学.商(cell, c); x = cell % c; // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 d = 0; 間 (d < 4 && !들어갈수있나(y + DY[d], x + DX[d])) { d += 1; } もし (d < 4) { ny = y + DY[d]; nx = x + DX[d]; visited[ny * c + nx] = 真; seen += 1; ch = grid[ny][nx]; もし (소문자인가(ch) && !keys.含む(ch)) { keys[ch] = 真; picked = picked + ch; } path.追加(ny * c + nx); } でなければ { もし (path.個数 == 1) { 抜ける; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 } path.位置で取り除く(path.個数 - 1); // 왔던 칸으로 한 칸 되돌아간다 } log.追加(path[path.個数 - 1]);}moves = log.個数 - 1;コンソール.書く(moves + " " + seen);コンソール.書く(picked.長さ > 0 ? picked : "-");それぞれ (t の中 queries){ at = log[数学.小さい方(t, moves)]; // 멈춘 뒤에는 처음 자리에 그대로 있다 コンソール.書く(数学.商(at, c) + 1 + " " + (at % c + 1));}