迷宫问题

import java.util.Scanner;
import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int rows = in.nextInt();
        int cols = in.nextInt();
        int[][] maze = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                maze[i][j] = in.nextInt();
            }
        }
        // 初始化
        int[] start = {0, 0};
        ArrayList<int[]> reached = new ArrayList<>();  // 已经走过的点
        ArrayList<int[]> frontier = new ArrayList<>();  // 尚未走过的边界
        frontier.add(start);
        // 深度优先搜索
        while (!frontier.isEmpty()) {
            int[] node = frontier.remove(frontier.size()-1);
            reached.add(node);
            if (node[0] == rows-1 && node[1] == cols-1) break;
            frontier.addAll(expand(reached, node, maze));
        }
        // 删去所有试错了的点（若相邻元素曼哈顿距离不为1，则删除所有中间的点）
        for (int i = 1; i < reached.size(); i++) {
            if (manhanton(reached.get(i), reached.get(i-1)) != 1) {
                reached.remove(--i);
                i--;
            }
        }
        for (int[] p : reached) {
            System.out.println("("+p[0]+","+p[1]+")");
        }
    }

    /* 尝试走一步 */
    public static ArrayList<int[]> expand(ArrayList<int[]> reached, int[] node, int[][] maze) {
        ArrayList<int[]> d = new ArrayList<>();
        int[] left = {node[0], node[1]-1};
        int[] up = {node[0]-1, node[1]};
        int[] right = {node[0], node[1]+1};
        int[] down = {node[0]+1, node[1]};
        int[][] move = {left, up, right, down};
        for (int i = 0; i < move.length; i++) {
            // 如果没碰壁、没越界、没走过，则加入frontier的后面
            if (move[i][0] >= 0 && move[i][1] >= 0 &&
                move[i][0] < maze.length && move[i][1] < maze[0].length &&
                maze[move[i][0]][move[i][1]] != 1 && !includes(reached, move[i])) {
                d.add(move[i]);
            }
        }
        return d;
    }

    public static boolean includes(ArrayList<int[]> arr, int[] ele) {
        for (int[] b : arr) {
            if (b[0] == ele[0] && b[1] == ele[1]) {
                return true;
            }
        }
        return false;
    }

    public static int manhanton(int[] a, int[] b) {
        // 计算两点之间的曼哈顿距离
        return Math.abs(a[0]-b[0]) + Math.abs(a[1]-b[1]);
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            int[][] c = new int[a][b];
            for (int i = 0; i < a; i++) {
                for (int j = 0; j < b; j++) {
                    c[i][j] = in.nextInt();
                }
            }
            List<String> list = new ArrayList<>();
            maze(a - 1, b - 1, 0, 0, c, list);
            for (int i = 1; i <= list.size(); i++) {
                System.out.println(list.get(list.size() - i));
            }
        }
    }
    private static void maze(int maxA, int maxB, int a, int b, int[][] c,
                             List<String> list) {
        if (maxA == a && maxB  == b) {
            list.add("(" + a + "," + b + ")");
            c[a][b] = 2 ;
            return;
        }
        c[a][b] = 1 ;
        if (a + 1 <= maxA && c[a + 1][b] == 0 && c[maxA][maxB]  != 2) {
            maze(maxA, maxB, a + 1, b, c, list);
        }
        if (a - 1 >= 0 && c[a - 1][b] == 0 && c[maxA][maxB]  != 2) {
            maze(maxA, maxB, a - 1, b, c, list);
        }
        if (b + 1 <= maxB && c[a][b + 1] == 0 && c[maxA][maxB]  != 2) {
            maze(maxA, maxB, a, b + 1, c, list);
        }
        if (b - 1 >= 0 && c[a][b - 1] == 0 && c[maxA][maxB]  != 2) {
            maze(maxA, maxB, a, b - 1, c, list);
        }
        if (c[maxA][maxB]  == 2) {
            list.add("(" + a + "," + b + ")");
            c[a][b] = 2 ;
        }
    }


}

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //!!!!不使用递归，纯用栈的方式实现dfs
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            int[][] miGong = new int[a][b];
            for (int i = 0; i < a; i++) {
                for (int j = 0; j < b; j++) {
                    miGong[i][j] = in.nextInt();
                }
            }
            //访问过的置为1
            Stack res = new Stack();
            res.push(new Main().new Node(0, 0));
            miGong[0][0] = 1;
            while (!res.isEmpty()) {
                Node s = res.peek();
                int x =  s.getI();
                int y =  s.getJ();
                if(x==a-1&&y==b-1){ //意味着到达终点
                    break;
                }
                int tag = 0;
                for (int i = 0; i < 4; i++) {
                    if (i == 0) {                   
                        if (x - 1 >= 0 && miGong[x - 1][y] != 1 && s.hasView[i] == 0) { //往上
                            s.hasView[i] = 1; //表示这个节点往上已经访问过了 
                            res.push(new Main().new Node(x - 1, y)); //把新的节点放进去
                            miGong[x-1][y]=1;
                            break;
                        } 
                        s.hasView[i] = 1; //表示这个节点往上已经访问过了    
                    } else if (i == 1) {                       
                        if (x + 1 < a && miGong[x + 1][y] != 1 && s.hasView[i] == 0) { //往下
                            s.hasView[i] = 1; //表示这个节点往下已经访问过了
                            res.push(new Main().new Node(x + 1, y));
                            miGong[x+1][y]=1;
                            break;
                        }
                        s.hasView[i] = 1; //表示这个节点往下已经访问过了
                    } else if (i == 2) {                        
                        if (y - 1 >= 0 && miGong[x][y - 1] != 1 && s.hasView[i] == 0) { //往左
                            s.hasView[i] = 1; //表示这个节点往左已经访问过了 
                            res.push(new Main().new Node(x, y - 1));
                            miGong[x][y-1]=1;
                            break;
                        } 
                        s.hasView[i] = 1; //表示这个节点往左已经访问过了 
                    } else if (i == 3) {                       
                        if (y + 1 < b && miGong[x][y + 1] != 1 && s.hasView[i] == 0) { //往右
                            s.hasView[i] = 1; //表示这个节点往右已经访问过了
                            res.push(new Main().new Node(x, y + 1));
                            miGong[x][y+1]=1;
                            break;
                        }
                        s.hasView[i] = 1; //表示这个节点往右已经访问过了                  
                    }
                    tag++;
                }
                //当for走完之后，都没有break; 意味着已经走不通了 tag==4
                //直接把这个节点弹出去
                if(tag==4){
                   miGong[x][y]=0;
                   res.pop(); 
                }  
            }
            Node[] show = new Node[res.size()];
            for(int i=show.length-1;i>=0;i--){
                show[i] = res.pop();
            }
            for(Node s : show){
                System.out.println("("+s.getI()+","+s.getJ()+")");
            } 
        }
    }
    class Node {
        int i;
        int j;
        int[] hasView = new int[4];//判断这个节点某个方向是否已经访问  这个方向已经走过了
        Node(int i, int j) {
            this.i = i;
            this.j = j;
        }
        int getI() {
            return i;
        }
        int getJ() {
            return j;
        }
    }
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int m;
    static int n;
    static int[][] graph;
    static int[][] offsets = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
    static int[] visited;
    static List<int[]> path;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        graph = new int[m][n];
        path = new ArrayList<>();

        visited = new int[m*n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = sc.nextInt();
            }
        }
        visited[0] = 1;
        if (dfs(0,0)) {
            for (int[] point : path) {
                System.out.println("(" + point[0] + "," + point[1] + ")");
            }
        }
    }

    private static boolean dfs(int i, int j) {
        path.add(new int[]{i,j});
        if (i==m-1 && j==n-1) {
            return true;
        }

        for (int[] offset : offsets) {
            int newX = i+offset[0];
            int newY = j+offset[1];
            int pos = newX * n + newY;

            if (newX<0 || newX>=m || newY<0 || newY>=n
                    || visited[pos]==1 || graph[newX][newY]==1) {
                continue;
            }
            visited[pos] = 1;
            if (dfs(newX, newY)) {
                return true;
            }
        }
        path.remove(path.size()-1);
        return false;
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int maze[][] = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                maze[i][j] = in.nextInt();
            }
        }
        int[][] seek = new int[n][m];//用于标记坐标点是否背探寻过，如果是探寻过的，则不再搜索
        Stack<int[]> ans = new Stack<>();//保存走过的路径
        ans.push(new int[]{0, 0});//起点
        seek[0][0] = 1;
        while(true) {
            int[] lastPos = ans.peek();
            //如果探寻的最新的点已经到达右下角，结束
            if (lastPos[0] == n - 1 && lastPos[1] == m - 1) break;
            //依次探寻左，上，右，下，如果四个方向都不可达，回退路径的上一个点重新探寻
            if (!canArrived(0, lastPos, ans, maze, seek) &&
                !canArrived(1, lastPos, ans, maze, seek) &&
                !canArrived(2, lastPos, ans, maze, seek) &&
                !canArrived(3, lastPos, ans, maze, seek)) {
                ans.pop();
            }
        }
        for (int[] an : ans) {
            System.out.println("(" + an[0] + "," + an[1] + ")");
        }
    }
    /**
     * 判断pos点是否可以向direction方向走是否可达
     * @param direction 0：向左，1：向上，2：向右，3：向下
     * @param lastPos 当前位置
     * @param ans 保存探寻到的路径
     * @param maze 迷宫
     * @param seek 是否已经探寻过
     * @return
     */
    public static boolean canArrived(int direction, int[] lastPos, Stack<int[]> ans, int[][] maze, int[][] seek) {
        boolean canArrived = false;
        int[] pos = new int[]{lastPos[0], lastPos[1]};
        switch (direction) {
            case 0:
                pos[1] -= 1;
                break;
            case 1:
                pos[0] -= 1;
                break;
            case 2:
                pos[1] += 1;
                break;
            case 3:
                pos[0] += 1;
                break;
            default:
                break;
        }
        if (pos[0] < 0 || pos[0] >= maze.length || pos[1] < 0 || pos[1] >= maze[0].length) {
            //越过边界
            canArrived = false;
        } else{
            //位置合法，且未被探寻过，且可达
            if (seek[pos[0]][pos[1]] != 1 && maze[pos[0]][pos[1]] == 0) {
                //未被探寻过，且可达
                ans.push(pos);
                canArrived = true;
            }
            //该点置为被探寻过
            seek[pos[0]][pos[1]] = 1;
        }
        return canArrived;
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {
    static String res; //最终结果
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        // 构造迷宫
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = in.nextInt();
            }
        }

        StringBuilder path = new StringBuilder();
        //初始坐标 0,0
        backTrack(arr, 0, 0, path);
        System.out.println(res);
    }

    // 递归回溯
    private static void backTrack(int[][] arr, int x, int y, StringBuilder path) {
        //跃出边界或者点位不为0则返回
        if (x < 0 || x >= arr.length || y < 0 || y >= arr[0].length || arr[x][y] != 0) {
            return;
        }

        //走到了最右下点位
        if (x == arr.length - 1 && y == arr[0].length - 1) {
            path.append("(" + x + "," + y + ")\n");
            res = path.toString();
            return;
        }

        //标记为已走过
        arr[x][y] = 1;
        path.append("(" + x + "," + y + ")\n");

        backTrack(arr, x, y - 1, path); //向上
        backTrack(arr, x, y + 1, path); //向下
        backTrack(arr, x - 1, y, path); //向左
        backTrack(arr, x + 1, y, path); //向右

        //回退
        path.delete(path.length() - 6, path.length());
        arr[x][y] = 0;
    }

}

import java.util.*;
public class Main {
    private static List<int[]> list = new ArrayList<>();
    private static boolean[][] flag;
    private static boolean win = false;
    private static void dfs(int[][] arr,int i,int j){
        // 不符合条件
        if (arr[i][j]==1||flag[i][j]){
            return;
        }
        // 找到出口
        if (i==arr.length-1&&j==arr[0].length-1){
            list.add(new int[]{i,j});
            win = true;
            return;
        }
        if(!win)
        list.add(new int[]{i,j});
        flag[i][j] = true;
        if (i>0){
            dfs(arr,i-1,j);
        }
        if (i< arr.length-1){
            dfs(arr,i+1,j);
        }
        if (j>0){
            dfs(arr,i,j-1);
        }
        if (j<arr[0].length-1){
            dfs(arr,i,j+1);
        }
        if (!win){
            list.remove(list.size()-1);
        }


    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] arr = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                arr[i][j] = sc.nextInt();
            }
        }
        flag = new boolean[m][n];
        dfs(arr,0,0);
        for (int i = 0; i < list.size(); i++) {
            System.out.println("("+list.get(i)[0]+","+list.get(i)[1]+")");
        }

    }
}

public class Test01 {
    //定义全局变量，用来收集结果
    static StringBuffer sb = new StringBuffer();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int[][] arr = new int[in.nextInt()][in.nextInt()];
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[0].length; j++) {
                    arr[i][j] = in.nextInt();
                }
            }
            dfs(arr,0,0,"");
            System.out.println(sb.toString());
        }
    }
    public static boolean dfs(int[][] arr,int i ,int j,String result){
        //下标越界
        if(i>arr.length-1||j>arr[0].length-1||i<0||j<0){
            return false;
        }
        //走出迷宫，使用全局变量收集结果。
        if(i==arr.length-1 && j==arr[0].length-1){
            sb.append(result);
            sb.append("("+i+","+j+")");
            return true;
        }
        //如果为0，表示可以走
        if(arr[i][j]==0){
            //标记已走过的路
            arr[i][j]=2;
            //result回溯结果
            if(dfs(arr,i-1,j,result+"("+i+","+j+")\n")){
                return true;
            }
            if(dfs(arr,i+1,j,result+"("+i+","+j+")\n")){
                return true;
            }
            if(dfs(arr,i,j-1,result+"("+i+","+j+")\n")){
                return true;
            }
            if(dfs(arr,i,j+1,result+"("+i+","+j+")\n")){
                return true;
            }
            //回溯
            arr[i][j]=0;
        }
        return false;
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] map = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    map[i][j] = in.nextInt();
                }
            }

            List<Position> path = new ArrayList<>();
            if(dfs(path, map, 0, 0)) {
                for (Position p : path) {
                    System.out.println("(" + p.x + "," + p.y + ")");
                }
            }
        }
    }

    public static boolean dfs(List<Position> path, int[][] map, int x, int y) {
        int n = map.length;
        int m = map[0].length;
        if (x < 0 || y < 0 || x >= n || y >= m) {
            return false;
        }
        if (map[x][y] == 1) return false;
        if (x == n - 1 && y == m - 1) {
            path.add(new Position(x, y));
            return true;
        }
        path.add(new Position(x, y));
        map[x][y] = 1;
        if (dfs(path, map, x + 1, y)) return true;
        if (dfs(path, map, x, y + 1)) return true;
        if (dfs(path, map, x - 1, y)) return true;
        if (dfs(path, map, x, y - 1)) return true;
        path.remove(path.size() - 1);
        map[x][y] = 0;
        return false;
    }

    public static class Position{
        int x;
        int y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

static LinkedList<Integer[]> goList = new LinkedList<>();
    static Integer[][] arr;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int widh = in.nextInt();
            int height = in.nextInt();

            arr = new Integer[height][widh];
            for (int i = 0; i < widh; i ++) {
                for (int j = 0; j <  height; j ++) {
                    arr[j][i] = in.nextInt();
                }
            }

            LinkedList<Integer[]> myList = new LinkedList<>();
            myList.add(new Integer[] {0, 0});
            getPath(myList);

            while(!goList.isEmpty()){
                Integer[] integers = goList.removeFirst();
                System.out.printf("(%s,%s)",integers[1],integers[0]);
                System.out.println();
            }
        }
    }

    public static void getPath(LinkedList<Integer[]> list) {

        Integer[] postion = list.getLast();
        if(postion[0] == arr.length-1 && postion[1] == arr[0].length-1 && (list.size()<goList.size() || goList.isEmpty())){
            goList = list;
            return;
        }
        // 向右
        Integer[] newPostion = null;
        if (postion[0]<arr.length-1  && isValid(list, newPostion = new Integer[] {postion[0] + 1, postion[1]})) {
            LinkedList<Integer[]> myList =  new LinkedList<>(list);
            myList.add(newPostion);
            getPath(myList);
        }
        // 向左
        if (postion[0]>0  && isValid(list, newPostion = new Integer[] {postion[0] - 1, postion[1]})) {
            LinkedList<Integer[]> myList =  new LinkedList<>(list);
            myList.add(newPostion);
            getPath(myList);
        }
        // 向上
        if (postion[1]>0  && isValid(list, newPostion = new Integer[] {postion[0] , postion[1]-1})) {
            LinkedList<Integer[]> myList =  new LinkedList<>(list);
            myList.add(newPostion);
            getPath(myList);
        }
        // 向下
        if (postion[1]<arr[0].length-1  && isValid(list, newPostion = new Integer[] {postion[0], postion[1] + 1})) {
            LinkedList<Integer[]> myList =  new LinkedList<>(list);
            myList.add(newPostion);
            getPath(myList);
        }
    }

    public static boolean isValid(LinkedList<Integer[]> list, Integer[] newPostion) {

        return arr[newPostion[0]][newPostion[1]] != 1 && !list.stream().anyMatch(item -> item[0] == newPostion[0] && item[1] == newPostion[1]);
    }

运行时间：19ms
超过88.64% 用Java提交的代码
占用内存：9628KB
超过93.21% 用Java提交的代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] mazeSize = br.readLine().split(" ");
        int n = Integer.parseInt(mazeSize[0]), m = Integer.parseInt(mazeSize[1]);
        int[][] maze = new int[n][m];
        for (int i = 0; i < n; i++) {
            String[] inputs = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                maze[i][j] = Integer.parseInt(inputs[j]);
            }
        }
        Solution sl = new Solution();
        System.out.println(sl.findPath(maze, n, m));
    }
}

class Solution {

    int n, m;
    int[][] maze;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public StringBuilder findPath(int[][] maze, int n, int m) {
        this.n = n;
        this.m = m;
        this.maze = maze;
        boolean[][] visited = new boolean[n][m];
        LinkedList<Integer> path = new LinkedList<>();
        dfs(path, visited, 0, 0);

        int size = path.size();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            sb.append("(").append(path.get(i++)).append(", ").append(path.get(i)).append(")\n");
        }
        return sb;
    }

    public void dfs(LinkedList<Integer> path, boolean[][] visited, int row, int col) {
        path.add(row);
        path.add(col);
        visited[row][col] = true;
        if (row == n - 1 && col == m - 1) {
            return;
        }
        for (int[] dir : dirs) {
            int nr = row + dir[0], nc = col + dir[1];

            if (nr >= 0 && nc >= 0 && nr < n && nc < m && !visited[nr][nc] && maze[nr][nc] == 0) {
                dfs(path, visited, nr, nc);
                if (visited[n - 1][m - 1]) {
                    return;
                }
                path.removeLast();
                path.removeLast();
            }
        }
    }
}