走迷宫

import java.util.*;
class Position{
    int x;
    int y;
    int level;
    public Position(int x,int y,int level){
        this.x = x;
        this.y = y;
        this.level = level;
    }
}
   

public class Main {
    public static int bfs(char[][] s,int m,int n){
    int[][] direc = {{-1,0},{0,1},{1,0},{0,-1}};
    //迷宫的入口和出口
    Position enter = new Position(0,1,0);
    Position out = new Position(9,8,0);
    
   //标记走过得数组
    boolean[][] flg = new boolean[m][n];
        
    //采用广度优先方式进行遍历
    Queue<Position> queue = new LinkedList<>();
    queue.offer(enter);
    while(!queue.isEmpty()){
        Position cur = queue.poll();
        flg[cur.x][cur.y] = true;
        
        //如果已经到了出口的位置，则直接返回
        if(cur.x == out.x && cur.y == out.y){
            return cur.level;
        }
        for(int i = 0;i < 4;i++){
            Position next = new Position(cur.x + direc[i][0],cur.y + direc[i][1],cur.level + 1);
            //数组下标没有越界，并且该点是合法路径，并且还没有被标记过
            if(next.x >= 0 && next.x < 10 && next.y >= 0 && next.y < 10 && 
               s[next.x][next.y] == '.' && !flg[next.x][next.y]){
                queue.offer(next);
            }
        }
        
    }
     return 0;
}
      public static void main(String[] args){
           Scanner sc = new Scanner(System.in);
          while(sc.hasNext()){
              char[][] map = new char[10][10];
              for(int i = 0;i < 10;i++){
                  String s = sc.next();
                  for(int j = 0;j < 10;j++){
                      map[i][j] = s.charAt(j);
                  }
              }
              System.out.println(bfs(map,10,10));
          }
      }       
}

// dfs深度优先搜索
import java.util.*;
public class Main{
    static int[][] direction = {{0,-1}, {-1,0}, {0,1}, {1,0}};
    public static void dfs(int x, int y, char[][] maze, int[][] map){
        for(int i = 0; i < 4; i++){
            int xx = x + direction[i][0];
            int yy = y + direction[i][1];
            if(xx >= 0 && xx < 10 && yy >= 0 && yy < 10 
              && maze[xx][yy] == '.' && map[xx][yy] > map[x][y]+1){
                map[xx][yy] = map[x][y] + 1;
                dfs(xx, yy, maze, map);
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            char[][] maze = new char[10][10];
            int[][] map = new int[10][10];
            for(int i = 0; i < 10; i++){
                String str = sc.next();
                for(int j = 0; j < 10; j++){
                    maze[i][j] = str.charAt(j);
                    map[i][j] = Integer.MAX_VALUE;
                }
            }
            map[0][1] = 0;
            dfs(0, 1, maze, map);
            System.out.println(map[9][8]);
        }
    }
}

// bfs广度优先搜索
import java.util.*;
public class Main{
    static int[][] direction = {{0,-1}, {-1,0}, {0,1}, {1,0}};
    static class Node{
        int x, y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            char[][] maze = new char[10][10];
            int[][] map = new int[10][10];
            boolean[][] visited = new boolean[10][10];
            for(int i = 0; i < 10; i++){
                String str = sc.next();
                for(int j = 0; j < 10; j++){
                    maze[i][j] = str.charAt(j);
                    if(maze[i][j] == '#'){
                        visited[i][j] = true;
                    }
                }
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(new Node(0, 1));
            while(!queue.isEmpty()){
                Node cur = queue.poll();
                for(int i = 0; i < 4; i++){
                    Node next = new Node(cur.x+direction[i][0], cur.y+direction[i][1]);
                    if(next.x >= 0 && next.x < 10 && next.y >= 0 && next.y < 10 
                      && !visited[next.x][next.y]){
                        queue.offer(next);
                        map[next.x][next.y] = map[cur.x][cur.y] + 1;
                        visited[next.x][next.y] = true;
                    }
                }
            }
            System.out.println(map[9][8]);
        }
    }
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextLine()) {
			Character[][] map = new Character[10][10];
			for (int i = 0; i < 10; i ++ ) {
				String s = sc.nextLine();
				for (int j = 0; j < 10; j ++ ) {
					map[i][j] = s.charAt(j);
				}
			}
			int[][] direction = {{0, 1}, {0, - 1}, {1, 0}, { - 1, 0}};
			Node start = new Node(0, 1, 0);
			Node end = new Node(9, 8, 0);
			bfs(map, direction, start, end);
		}
	}
	public static void bfs(Character[][] map, int[][] direction, Node start, Node end) {
		boolean[][] visited = new boolean[map.length][map[0].length];
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(start);
		visited[start.x][start.y] = true;
		while ( ! queue.isEmpty()) {
			Node cur = queue.poll();
			if(cur.x == end.x && cur.y == end.y) {
				System.out.println(cur.step);
				break;
			}
			for (int i = 0; i < 4; i ++ ) {
				Node next = new Node(cur.x + direction[i][0], cur.y + direction[i][1], cur.step + 1);
				if(next.x >= 0 && next.x < map.length && next.y >= 0 && next.y < map[0].length && ! visited[next.x][next.y] && map[next.x][next.y] != '#') {
					queue.add(next);
					visited[next.x][next.y] = true;
				}
			}
		}
	}
	static class Node {
		int x;
		int y;
		int step;
		public Node(int x, int y, int step) {
			this.x = x;
			this.y = y;
			this.step = step;
		}
	}
}