棋盘的最短路径（障碍物、广度优先）

图的遍历常用来寻找最优路径，其中有一个经典的棋盘问题。

问题描述：矩阵A代表棋盘，棋盘上散列了未知数目的障碍物（位于值为1的坐标上），你每次只能左右移动或者垂直移动一个单位，你需要找出从起始点坐标到终点坐标的最短路径。

我们知道图的遍历方式有广度和深度，而寻找最短路径时利用广度优先可以更快找到，且节省了栈的空间；

思路如下：

1、判断起始点与终点坐标相等则返回0，无需移动，否则继续；

2、将起始节点入队,队列每个元素保存的是{y,x,当前走过的步长step}；

3、在循环体中，将队头元素出队，取坐标x,y，并将坐标存入哈希表（以判断是否已经路过）。

对这个坐标的上、下、左、右元素都做判断，

如果有一个是目标节点则返回到达它的步长；

否则将该坐标存入队尾，并且其对应步长+1；

实现代码如下：

package com.Graph;

import org.junit.Test;
import java.util.*;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class BFS {
    @Test
    public void test() {
        int[][] graph = new int[][]{{0, 0, 0, 0, 0},
                                    {0, 0, 1, 1, 0},
                                    {0, 0, 1, 0, 0},
                                    {0, 0, 1, 0, 0}};

//        计算（[0][0]到[2][3]的最短路径，1是障碍物）
        int[] start = {0, 0};
        int[] end = {2, 3};
        System.out.println(shortestStep(graph, start, end));
        v.add("0234");
        System.out.println(v.contains(String.valueOf(0)+String.valueOf(234-1+1)));
    }


    public int shortestStep(int[][] g, int[] start, int[] end) {
        if(start[0]==end[0]&&start[1]==end[1])
            return 0;
        int ylen = g.length, xlen = g[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited=new boolean[ylen][xlen];
        queue.offer(new int[]{start[0],start[1],1});
//        使用队列先进先出
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int x = pos[1], y = pos[0];
            visited[y][x]=true;
            System.out.println(Arrays.toString(pos));
//          左
            if (x - 1 >= 0 && g[y][x - 1] != 1 && !visited[y][x-1])
            {
                if (y == end[0] && x - 1 == end[1]) return pos[2];
                else queue.offer(new int[]{y, x - 1, pos[2] + 1});
            }
//          右
            if (x + 1 < xlen && g[y][x + 1] != 1 && !visited[y][x+1]) {
                if (y == end[0] && x + 1 == end[1]) return pos[2];
                else queue.offer(new int[]{y, x + 1,pos[2]+1});
            }
//          上
            if (y - 1 >= 0 && g[y - 1][x] != 1 && !visited[y-1][x]){
                if (y - 1 == end[0] && x == end[1]) return pos[2];
                else queue.offer(new int[]{y - 1, x,pos[2]+1});}
//          下
            if (y + 1 < ylen && g[y + 1][x] != 1 && !visited[y+1][x]) {
                if (y + 1 == end[0] && x == end[1]) return pos[2];
                else queue.offer(new int[]{y + 1, x, pos[2] + 1});
            }
        }
//        代表不可达
        return -1;
    }


}