水陆距离 （C++代码）

解题思路:
        

        广搜题。

                把所有的 0 点放进队列，从 0 点开始拓展，每一步步长 +1 即是所求距离。比每一个点都搜一次快很多。

参考代码:

#include<bits/stdc++.h>
using namespace std;

int MapH, MapD;
char Map[101][101];          /*    存储图    */
bool Vis[101][101];          /*   标记数组   */
int  Res[101][101];          /*   结果数组   */
int moveX[] = { 1, 0, -1, 0};/*     方向     */
int moveY[] = { 0, -1, 0, 1};

typedef struct {             /* 当前状态数据 */
	int posx, posy, step;
} pos;

bool check(pos poi){         /*   剪枝条件   */
	if(poi.posx >= 0 && poi.posx < MapH)
		if(poi.posy >= 0 && poi.posy < MapD)
			if(Vis[poi.posx][poi.posy] != true)
				return true;
	return false;
}

int main() {
	queue<pos> que;
	cin >> MapH >> MapD;

	for(int i1 = 0; i1 < MapH; i1++)
		for(int i2 = 0; i2 < MapD; i2++){
			cin >> Map[i1][i2];
			/*   0 值入列，标记已走过    */
			if(Map[i1][i2] == '0'){
				pos poi = {i1, i2, 0};
				Vis[i1][i2] = true;
				que.push(poi);
			}	
		}

	while(!que.empty()) {
		pos now = que.front();
		que.pop();

		for(int i = 0; i < 4; i++){
			now.posx += moveX[i]; now.posy += moveY[i]; now.step++;
			if(check(now)){ 
				/*     所求距离就是当前步长     */
				Res[now.posx][now.posy] = now.step;
				/*          标记已走过          */
				Vis[now.posx][now.posy] = true;
				/*             入列             */
				que.push(now);
			}
			/*      回溯状态     */
			now.posx -= moveX[i]; now.posy -= moveY[i]; now.step--;
		} 
	}

	for(int posx = 0; posx < MapH; posx++){
		for(int posy = 0; posy < MapD; posy++)
			cout << Res[posx][posy] << ' ';
		cout << endl;
	}
	return 0;
}