BFS广度优先搜索

迷宫最短路径

输入格式为

15
0 7 7 7
*5#++B+B+++++$3
55#+++++++###$$
###$++++++#+*#+
++$@$+++$$$3+#+
+++$$+++$+4###+
A++++###$@+$++A
+++++#++$#$$+++
A++++#+5+#+++++
+++$$#$++#++++A
+++$+@$###+++++
+###4+$+++$$+++
+#+3$$$+++$##++
+#*+#++++++#$$+
$####+++++++$##
3$+++B++B++++#5
第一行为矩阵阶数
第二行为开始和终点坐标
剩下为矩阵

package testDemo;

import java.util.*;
import java.awt.Point;
import java.io.*;

public class Main1 {

    static int[][] map;
    static int[][] book;
    public static void main(String args[])throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            int n = Integer.parseInt(line);
            String[] ars = br.readLine().split(" ");
            //开始xy
            int sx = Integer.parseInt(ars[0]);
            int sy = Integer.parseInt(ars[1]);
            //结束xy
            int ex = Integer.parseInt(ars[2]);
            int ey = Integer.parseInt(ars[3]);
            //地图
            map = new int[n][n];
            book = new int[n][n];

            for(int i = 0;i < n;i++){
                String t = br.readLine();
                for(int j = 0;j < t.length();j++){
                    char c = t.charAt(j);
                    if(c == '#' || c == '@'){
                        map[i][j] = 1;
                    }else{
                        map[i][j] = 0;
                    }
                    if(i == sx && j == sy){
                        book[i][j] = 0; 
                    }else{
                        book[i][j] = Integer.MAX_VALUE; 
                    }
                }
            }
            //这行以上都是处理输入输出


            Point p = new Point();
            p.x = sx;
            p.y = sy;
            int cnt = bfs(p, ex, ey, n);
            if(cnt == Integer.MAX_VALUE){
                System.out.println(-1);
            }else{
                System.out.println(cnt);
            }
        }
    }

    public static int bfs(Point t,int ex,int ey,int n){
        int arr3[] = {0,-1,0,1};
        int arr4[] = {-1,0,1,0};
        Deque<Point> que = new LinkedList<Point>();
        que.add(t);
        while(!que.isEmpty()){
            Point p = que.poll();

            if(p.x == ex && p.y == ey){
                return book[p.x][p.y];
            }

            for (int i=0;i<4;i++) {
                int x = p.x+arr3[i];
                int y = p.y+arr4[i];
                if(x>=0&&y>=0&&x<n&&y<n&&book[x][y]==Integer.MAX_VALUE&&map[x][y]==0) {
                    que.add(new Point(x,y));
                    book[x][y]=book[p.x][p.y]+1;
                }
            }

        }
        return Integer.MAX_VALUE;
    }
}

NC109

import java.util.*;


public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */

    public int solve (char[][] grid) {
        // 岛屿数量
        int nums = 0;   
        // 0 没走过；1 走过
        byte[][] flag = new byte[grid.length][grid[0].length];
        LinkedList<Point> points = new LinkedList<>();
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                // 找到一个没走过的岛屿起始点
                if(grid[i][j] == '1' && flag[i][j] == 0) {
                    points.add(new Point(i, j));
                    flag[i][j] = 1;
                    nums++;
                    while(!points.isEmpty()) {
                        Point t = points.pollFirst();
                        int x = t.x;
                        int y = t.y;
                        // 四周的点加入队列
                        if(x - 1 >= 0 && x - 1 < grid.length && grid[x - 1][y] == '1' && flag[x - 1][y] == 0) {
                            flag[x - 1][y] = 1;
                            points.add(new Point(x - 1, y));
                        }
                        if(x + 1 >= 0 && x + 1 < grid.length && grid[x + 1][y] == '1' && flag[x + 1][y] == 0) {
                            flag[x + 1][y] = 1;
                            points.add(new Point(x + 1, y));
                        }
                        if(y - 1 >= 0 && y - 1 < grid[0].length && grid[x][y - 1] == '1' && flag[x][y - 1] == 0) {
                            flag[x][y - 1] = 1;
                            points.add(new Point(x, y - 1));
                        }
                        if(y + 1 >= 0 && y + 1 <grid[0].length && grid[x][y + 1] == '1' && flag[x][y + 1] == 0) {
                            flag[x][y + 1] = 1;
                            points.add(new Point(x, y + 1));
                        }
                    }
                }
            }
        }
        return nums;
    }
}