题解 | #地下迷宫#

#include <bits/stdc++.h>
using namespace std;

// 方向数组
const int dirx[] = {-1, 0, 1, 0};  // 上右下左
const int diry[] = {0, 1, 0, -1};
const int value[] = {3, 1, 0, 1};  // 对应方向的体力消耗

// 节点结构
struct Node {
    int x, y;    // 坐标
    int p;       // 剩余体力
    int pre;     // 前驱节点索引
    
    Node(int x, int y, int p, int pre = -1) 
        : x(x), y(y), p(p), pre(pre) {}
    
    bool operator < (const Node &other) const {
        return p > other.p;
    }
};

int main() {
    int n, m, p;
    while(cin >> n >> m >> p) {
        // 读入迷宫地图
        vector<vector<int>> mp(n, vector<int>(m));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cin >> mp[i][j];
            }
        }
        
        // BFS搜索
        deque<Node> que;
        vector<vector<bool>> used(n, vector<bool>(m, false));
        que.push_back(Node(0, 0, p));
        used[0][0] = true;
        
        int head = 0;
        bool found = false;
        int ans = 0;
        
        while(!que.empty() && head < que.size()) {
            auto now = que[head++];
            
            // 到达终点
            if(now.x == 0 && now.y == m-1) {
                found = true;
                ans = head - 1;
                break;
            }
            
            // 尝试四个方向
            for(int i = 0; i < 4; i++) {
                int tx = now.x + dirx[i];
                int ty = now.y + diry[i];
                int tp = now.p - value[i];
                
                // 判断是否可以移动
                if(tx >= 0 && tx < n && ty >= 0 && ty < m && 
                   mp[tx][ty] == 1 && !used[tx][ty] && tp >= 0) {
                    que.push_back(Node(tx, ty, tp, head-1));
                    used[tx][ty] = true;
                }
            }
        }
        
        // 输出结果
        if(!found) {
            cout << "Can not escape!" << endl;
        } else {
            // 重建路径
            stack<int> st;
            while(que[ans].pre != -1) {
                st.push(que[ans].pre);
                ans = que[ans].pre;
            }
            
            // 输出路径
            while(!st.empty()) {
                cout << "[" << que[st.top()].x << "," 
                     << que[st.top()].y << "],";
                st.pop();
            }
            cout << "[0," << m-1 << "]" << endl;
        }
    }
    return 0;
}

import java.util.*;

public class Main {
    // 方向数组
    static int[] dirx = {-1, 0, 1, 0};  // 上右下左
    static int[] diry = {0, 1, 0, -1};
    static int[] value = {3, 1, 0, 1};  // 对应方向的体力消耗
    
    // 节点类
    static class Node {
        int x, y, p, pre;
        
        Node(int x, int y, int p, int pre) {
            this.x = x;
            this.y = y;
            this.p = p;
            this.pre = pre;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int p = sc.nextInt();
            
            // 读入迷宫地图
            int[][] mp = new int[n][m];
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    mp[i][j] = sc.nextInt();
                }
            }
            
            // BFS搜索
            List<Node> que = new ArrayList<>();
            boolean[][] used = new boolean[n][m];
            que.add(new Node(0, 0, p, -1));
            used[0][0] = true;
            
            int head = 0;
            boolean found = false;
            int ans = 0;
            
            while(head < que.size()) {
                Node now = que.get(head++);
                
                if(now.x == 0 && now.y == m-1) {
                    found = true;
                    ans = head - 1;
                    break;
                }
                
                for(int i = 0; i < 4; i++) {
                    int tx = now.x + dirx[i];
                    int ty = now.y + diry[i];
                    int tp = now.p - value[i];
                    
                    if(tx >= 0 && tx < n && ty >= 0 && ty < m && 
                       mp[tx][ty] == 1 && !used[tx][ty] && tp >= 0) {
                        que.add(new Node(tx, ty, tp, head-1));
                        used[tx][ty] = true;
                    }
                }
            }
            
            if(!found) {
                System.out.println("Can not escape!");
            } else {
                StringBuilder sb = new StringBuilder();
                Stack<Integer> st = new Stack<>();
                sb.append("[0,0],");
                while(que.get(ans).pre != -1) {
                    st.push(ans);
                    ans = que.get(ans).pre;
                }
                
                while(!st.isEmpty()) {
                    Node node = que.get(st.pop());
                    sb.append("[").append(node.x).append(",")
                      .append(node.y).append("],");
                    if (node.x == 0 && node.y == m-1) {
                        sb.deleteCharAt(sb.length() - 1);
                    }
                }
                System.out.println(sb.toString());
            }
        }
    }
}

from collections import deque
from typing import List, Tuple

# 方向数组
DIRS = [(-1,0), (0,1), (1,0), (0,-1)]  # 上右下左
VALUES = [3, 1, 0, 1]  # 对应方向的体力消耗

class Node:
    def __init__(self, x: int, y: int, p: int, pre: int = -1):
        self.x = x
        self.y = y
        self.p = p
        self.pre = pre

def solve(n: int, m: int, p: int, mp: List[List[int]]) -> str:
    # BFS搜索
    que = deque([Node(0, 0, p)])
    used = [[False] * m for _ in range(n)]
    used[0][0] = True
    nodes = [Node(0, 0, p)]  # 存储所有节点
    head = 0
    found = False
    ans = 0
    
    while head < len(nodes):
        now = nodes[head]
        head += 1
        
        if now.x == 0 and now.y == m-1:
            found = True
            ans = head - 1
            break
        
        for i, (dx, dy) in enumerate(DIRS):
            tx = now.x + dx
            ty = now.y + dy
            tp = now.p - VALUES[i]
            
            if (0 <= tx < n and 0 <= ty < m and 
                mp[tx][ty] == 1 and not used[tx][ty] and tp >= 0):
                nodes.append(Node(tx, ty, tp, head-1))
                used[tx][ty] = True
    
    if not found:
        return "Can not escape!"
    
    # 重建路径
    path = []
    while nodes[ans].pre != -1:
        path.append(f"[{nodes[ans].x},{nodes[ans].y}]")
        ans = nodes[ans].pre
    
    path.append(f"[0,{0}]")
    return ','.join(path[::-1])

def main():
    while True:
        try:
            n, m, p = map(int, input().split())
            mp = []
            for _ in range(n):
                mp.append(list(map(int, input().split())))
            print(solve(n, m, p, mp))
        except EOFError:
            break

if __name__ == "__main__":
    main()