BFS

DFS

package nowcoder.com;

import java.util.*;

/**
 * Created by Administrator on 2016/8/26.
 */
public class Maze {
    static int[] moveRow = {0, 1, 0, -1};
    static int[] moveCol = {1, 0, -1, 0};// 0 1 4 ， 

    static class MazeNode {// ， 
        public int row;
        public int col;
        public MazeNode pre;

        public MazeNode(int row, int col) {
            this.row = row;
            this.col = col;
        }

        @Override
        public String toString() {// toString ，print 
            return "(" + row + "," + col + ")";
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int ROW = scanner.nextInt();
            int COL = scanner.nextInt();
            int[][] maze = new int[ROW][COL];// 
            for (int i = 0; i < ROW; i++) {
                for (int j = 0; j < COL; j++) {
                    maze[i][j] = scanner.nextInt();
                }
            }
            MazeNode start = new MazeNode(0, 0);
            ArrayList result = solution(maze,start);// 
//            ArrayList result = solution1(maze, start);
//            for (int i = result.size() - 1; i >= 0; i--) {
//                System.out.println(result.get(i));
//            }

            for (int i = 0; i < result.size(); i++) {
                System.out.println(result.get(i));

            }
        }
    }

    private static ArrayList solution1(int[][] maze, MazeNode start) {// 
        ArrayList list = new ArrayList<>();
        MazeNode node = new MazeNode(0, 0);
        int row = maze.length;
        int col = maze[0].length;
        boolean mark[][] = new boolean[row][col];
        BFS(maze, start, mark, list, node);
        ArrayList result = new ArrayList<>();
        while (node.row != 0 || node.col != 0) {
            result.add(node);
            node = node.pre;
        }
        result.add(new MazeNode(0, 0));
        return result;
    }

    private static void BFS(int[][] maze, MazeNode start, boolean[][] mark, ArrayList list, MazeNode end) {
        Queue queue = new LinkedList<>();
        queue.add(start);//BFS 
        while (!queue.isEmpty()) {
            MazeNode node = queue.poll();// 
            list.add(node);
            if (node.row == maze.length - 1 && node.col == maze[0].length - 1) {
                end.col = node.col;
                end.row = node.row;
                end.pre = node.pre;
                return;
            }
            int i = node.row;
            int j = node.col;
            mark[i][j] = true;// 

            for (int k = 0; k < 4; k++) {//for ， r 
                int tmpi = i + moveRow[k];
                int tmpj = j + moveCol[k];
                if (tmpi >= 0 && tmpi < maze.length && tmpj >= 0 && tmpj < maze[0].length && maze[tmpi][tmpj] == 0 && !mark[tmpi][tmpj]) {
                    MazeNode node1 = new MazeNode(tmpi, tmpj);
                    node1.pre = node;
                    list.add(node1);
                    queue.add(node1);
                }
            }
        }
    }


    private static ArrayList solution(int[][] maze, MazeNode start) {
        int row = maze.length;
        int col = maze[0].length;
        boolean mark[][] = new boolean[row][col];
        ArrayList path = new ArrayList<>();
        ArrayList result = new ArrayList<>();
        DFS(maze, start, mark, path, result);
        return result;
    }

    private static void DFS(int[][] maze, MazeNode start, boolean[][] mark, ArrayList path, ArrayList result) {

        if (start.col == maze[0].length - 1 && start.row == maze.length - 1) {
            path.add(new MazeNode(maze.length - 1, maze[0].length - 1));
            int size = path.size();
            for (int i = 0; i < size; i++) {
                result.add(path.get(i));
            }
        }
        int i = start.row, j = start.col;
        mark[start.row][start.col] = true;
        path.add(start);
        for (int k = 0; k < 4; k++) {
            int tmpi = i + moveRow[k];
            int tmpj = j + moveCol[k];
            if (tmpi >= 0 && tmpi < maze.length && tmpj >= 0 && tmpj < maze[0].length && maze[tmpi][tmpj] == 0 && !mark[tmpi][tmpj]) {
                MazeNode node1 = new MazeNode(tmpi, tmpj);
               // while(!path.isEmpty())  path.add(node1);
                DFS(maze, node1, mark, new ArrayList<>(path), result);// DFS
            }
        }
    }
}