参考第34页-36页

题目：

给定一个大小为N*M的迷宫，由通道('.')和墙壁('#')组成，其中通道S表示起点，通道G表示终点，每一步移动可以达到上下左右中不是墙壁的位置。试求出起点到终点的最小步数。（本题假定迷宫是有解的）

(N,M<=100)

样例输入：

10 10

# S # # # # # # . #

. . . . . . # . . #

. # . # # . # # . #

. # . . . . . . . .

# # . # # . # # # #

. . . . # . . . . #

. # # # # # # # . #

. . . . # . . . . .

. # # # # . # # # .

. . . . # . . . G #

样例输出：

22

---

 

题解：

宽度优先搜索按照距开始状态由近及远的顺序进行搜索,因此可以很容易地用来求最短路径、最少操作之类问题的答案。这个问题中,状态仅仅是目前所在位置的坐标,因此可以构造成pair或者编码成int来表达状态。当状态更加复杂时,就需要封装成一个类来表示状态了。转移的方式为四方向移动,状态数与迷宫的大小是相等的,所以复杂度是O(4×N×M)=O(N×M)。

宽度优先搜索中,只要将已经访问过的状态用标记管理起来,就可以很好地做到由近及远的搜索。这个问题中由于要求最短距离,不妨用d[N][M]数组把最短距离保存起来。初始时用充分大的常数INF来初始化它,这样尚未到达的位置就是INF,也就同时起到了标记的作用。

虽然到达终点时就会停止搜索,可如果继续下去直到队列为空的话,就可以计算出到各个位置的最短距离。此外,如果搜索到最后,d依然为INF的话,便可得知这个位置就是无法从起点到达的位置。

在今后的程序中,使用像INF这样充分大的常数的情况还很多。不把INF当作例外,而是直接参与普通运算的情况也很常见。这种情况下,如果INF过大就可能带来溢出的危险。

假设INF=2^31-1。例如想用d[nx][ny]=min(d[nx][ny],d[x][y]+1)来更新d[nx][ny],就会发生INF+1=-2^31的情况。这一问题中d[x][y]总不等于INF,所以没有问题。但是为了防止这样的问题,一般会将INF设为放大2~4倍也不会溢出的大小。

因为要向4个不同方向移动,用dx[4]和dy[4]两个数组来表示四个方向向量。这样通过一个循环就可以实现四个方向移动的遍历。

c++版本代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAX_N = 100;const int MAX_M = 100;const int INF = 0x3f3f3f3f;typedef pair
        
          P;char maze[MAX_N][MAX_M + 1];int N, M;int sx, sy; //起点的位置int gx, gy; //终点的位置int d[MAX_N][MAX_M];//储存起点到某一点的距离int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; //表明每次x和y方向的位移void bfs(){    queue
         
 que;    for (int i = 0; i < N; i++)        for (int j = 0; j < M; j++)            d[i][j] = INF;	//初始化所有点的距离为INF    que.push(P(sx, sy));    d[sx][sy] = 0;	//从起点出发将距离设为0，并放入队列首端    while (que.size()) //题目保证有路到终点，所以不用担心死循环    {        P p = que.front(); que.pop();//弹出队首元素        if(p.first == gx&&p.second == gy) break; //已经到达终点则退出        for (int i = 0; i < 4; i++)        {            int nx = p.first + dx[i];            int ny = p.second + dy[i];//移动后的坐标            //判断可移动且没到过            if (0 <= nx&&nx < N                && 0 <= ny&&ny < M                &&maze[nx][ny] != '#'                &&d[nx][ny] == INF)//之前到过的话不用考虑，因为距离在队列中递增，肯定不会获得更好的解            {                que.push(P(nx, ny));	//可以移动则设定距离为之前加一，放入队列                d[nx][ny] = d[p.first][p.second] + 1;            }        }    }}int main(){    scanf("%d %d",&N,&M);    for (int n = 0; n < N; n++){        for (int j = 0; j < M; j++)        {            scanf("%s",&maze[n][j]);        }    }    for (int i = 0; i < N; i++)        for (int j = 0; j < M; j++)        {            if (maze[i][j] == 'S')            {                sx = i; sy = j;            }            if (maze[i][j] == 'G')            {                gx = i; gy = j;            }        }    bfs();    printf("%d\n",d[gx][gy]);    return 0;}
        
       
      
     

　Java版代码

package 宽度优先搜索;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Main {	static	class Point{		int x;		int y;		public int getX() {			return x;		}		public void setX(int x) {			this.x = x;		}		public int getY() {			return y;		}		public void setY(int y) {			this.y = y;		}		public Point(int x, int y) {			this.x = x;			this.y = y;		}	}	public static void main(String[] args) {		Scanner sc = new Scanner(System.in);		int N = sc.nextInt();		int M = sc.nextInt();		String maze[][] = new String[N][M];		for (int i = 0; i < maze.length; i++) {			for (int j = 0; j < maze[0].length; j++) {				maze[i][j] = sc.next();			}		}		bfs(maze);	}	private static void bfs(String[][] maze) {		int INF=100000;		int N = maze.length;		int M = maze[0].length;		int res[][]=new int[N][M];		int sx = 0, sy = 0; // 起点的位置		int gx = 0, gy = 0; // 终点的位置		for (int i = 0; i < N; i++) {			for (int j = 0; j < M; j++) {				if (maze[i][j].equals("S")) {					sx = i;					sy = j;				}				if (maze[i][j].equals("G")) {					gx = i;					gy = j;				}			}		}		for (int i = 0; i < N; i++) {			for (int j = 0; j < M; j++) {				res[i][j]=INF;			}		}		Point start=new Point(sx, sy);		Queue
     
       queue=new LinkedList<>();		queue.add(start);		res[sx][sy]=0;//将起始点设置为0		while (!queue.isEmpty()) {						int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }; //表明每次x和y方向的位移			Point tmp=queue.poll();			if(tmp.x == gx&&tmp.y == gy) break; //已经到达终点则退出			for (int i = 0; i < dx.length; i++) {				int nx = tmp.x + dx[i];				int ny = tmp.y + dy[i];//移动后的坐标				if (0 <= nx&&nx < N						&& 0 <= ny&&ny < M						&&!maze[nx][ny].equals("#")						&&res[nx][ny] ==INF)//之前到过的话不用考虑，因为距离在队列中递增，肯定不会获得更好的解				{					 queue.add(new Point(nx, ny));    //可以移动则设定距离为之前加一，放入队列		             res[nx][ny] = res[tmp.x][tmp.y] + 1;				}			}		}		System.out.println(res[gx][gy]);	}}