题解 | #迷宫问题#

#include <iostream>
#include <vector>
using namespace std;

class Solution {
private:
    vector<pair<int, int>> path;
    vector<vector<bool>> visited;
    
    bool dfs(vector<vector<int>>& maze, int x, int y, int n, int m) {
        if (x == n-1 && y == m-1) {
            path.push_back({x, y});
            return true;
        }
        
        if (x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == 1 || visited[x][y]) {
            return false;
        }
        
        visited[x][y] = true;
        path.push_back({x, y});
        
        if (dfs(maze, x, y+1, n, m) || dfs(maze, x+1, y, n, m) || dfs(maze, x, y-1, n, m) || dfs(maze, x-1, y, n, m)) {
            return true;
        }
        
        path.pop_back();
        visited[x][y] = false;
        return false;
    }
    
public:
    vector<pair<int, int>> findPath(vector<vector<int>>& maze) {
        int n = maze.size();
        int m = maze[0].size();
        visited = vector<vector<bool>>(n, vector<bool>(m, false));
        path.clear();
        
        dfs(maze, 0, 0, n, m);
        return path;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> maze(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
        }
    }
    
    Solution solution;
    vector<pair<int, int>> path = solution.findPath(maze);
    
    for (const auto& point : path) {
        cout << "(" << point.first << "," << point.second << ")" << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    private static List<int[]> path = new ArrayList<>();
    private static boolean[][] visited;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[][] maze = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                maze[i][j] = sc.nextInt();
            }
        }
        
        visited = new boolean[n][m];
        dfs(maze, 0, 0, n, m);
        
        for (int[] point : path) {
            System.out.println("(" + point[0] + "," + point[1] + ")");
        }
    }
    
    private static boolean dfs(int[][] maze, int x, int y, int n, int m) {
        if (x == n-1 && y == m-1) {
            path.add(new int[]{x, y});
            return true;
        }
        
        if (x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == 1 || visited[x][y]) {
            return false;
        }
        
        visited[x][y] = true;
        path.add(new int[]{x, y});
        
        if (dfs(maze, x, y+1, n, m) || dfs(maze, x+1, y, n, m) || dfs(maze, x, y-1, n, m) || dfs(maze, x-1, y, n, m)) {
            return true;
        }
        
        path.remove(path.size()-1);
        visited[x][y] = false;
        return false;
    }
}

def find_path(maze):
    n = len(maze)
    m = len(maze[0])
    visited = [[False] * m for _ in range(n)]
    path = []
    result = []
    
    def dfs(x, y):
        # 如果到达终点
        if x == n-1 and y == m-1:
            result.extend(path + [(x, y)])
            return True
            
        # 检查当前位置是否可行
        if (x < 0 or x >= n or y < 0 or y >= m or 
            maze[x][y] == 1 or visited[x][y]):
            return False
            
        visited[x][y] = True
        path.append((x, y))
        
        # 向右和向下搜索
        if dfs(x, y+1) or dfs(x+1, y) or dfs(x, y-1) or dfs(x-1, y):
            return True
            
        path.pop()
        visited[x][y] = False
        return False
    
    dfs(0, 0)
    return result

# 处理输入
n, m = map(int, input().split())
maze = []
for _ in range(n):
    maze.append(list(map(int, input().split())))

# 获取路径并输出
path = find_path(maze)
for point in path:
    print(f"({point[0]},{point[1]})")