Exploring a cave by feel, picking up keys

import sys data = 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 True  while 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))

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"));

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"));

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);    }}

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_);    }}

#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";    }}

#include <ctype.h>#include <stdio.h> #define MAXN 50 static 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;}

첫줄 = Console.ReadNumbers();r = 첫줄[0];c = 첫줄[1];grid = [];start = 0; // 칸은 수 하나(y * c + x)로 다룬다for (y = 0; y < r; y++){    줄 = Console.ReadLine().Trim();    grid.Add(줄);    x = 줄.IndexOf("S");    if (x >= 0)    {        start = y * c + x;    }}q = Console.ReadLine().Trim().ToNumber();queries = Console.ReadNumbers(); DY = [-1, 0, 1, 0]; // 위, 오른쪽, 아래, 왼쪽DX = [0, 1, 0, -1];visited = NewList(r * c, false);visited[start] = true;keys = Dict();picked = ""; // 새로 얻은 열쇠(얻은 차례) 대문자인가(ch){    return ch >= "A" && ch <= "Z";} 소문자인가(ch){    return ch >= "a" && ch <= "z";} 들어갈수있나(y, x){    if (y < 0 || y >= r || x < 0 || x >= c)    {        return false;    }    if (visited[y * c + x])    {        return false;    }    ch = grid[y][x];    if (ch == "#")    {        return false;    }    if (대문자인가(ch))    {        return keys.Contains(ch.ToLower()); // 문은 맞는 열쇠가 있어야 들어간다    }    return true;} path = [start]; // 지금까지 들어온 길(스택): 맨 끝이 지금 자리log = [start]; // log[t] = t번 움직인 뒤의 자리seen = 1;while (true){    cell = path[path.Count - 1];    y = Mathf.Quot(cell, c);    x = cell % c;    // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다    d = 0;    while (d < 4 && !들어갈수있나(y + DY[d], x + DX[d]))    {        d += 1;    }    if (d < 4)    {        ny = y + DY[d];        nx = x + DX[d];        visited[ny * c + nx] = true;        seen += 1;        ch = grid[ny][nx];        if (소문자인가(ch) && !keys.Contains(ch))        {            keys[ch] = true;            picked = picked + ch;        }        path.Add(ny * c + nx);    }    else    {        if (path.Count == 1)        {            break; // 처음 자리에서 더 갈 곳이 없으면 멈춘다        }        path.RemoveAt(path.Count - 1); // 왔던 칸으로 한 칸 되돌아간다    }    log.Add(path[path.Count - 1]);} moves = log.Count - 1;Console.WriteLine(moves + " " + seen);Console.WriteLine(picked.Length > 0 ? picked : "-");foreach (t in queries){    at = log[Mathf.Min(t, moves)]; // 멈춘 뒤에는 처음 자리에 그대로 있다    Console.WriteLine(Mathf.Quot(at, c) + 1 + " " + (at % c + 1));}