HDU - 1728 逃离迷宫

题意：

 2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3 

Sample Output

 no
yes 

方法，计算出最少的拐弯次数，并不是计算出最短的路程

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int r,c,sx,sy,ex,ey,wan[MAXN][MAXN],k;
char map[MAXN][MAXN];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,1,-1};
struct node{
	int x,y;
};

void bfs(){
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			wan[i][j] = INF;
	node a,tmp;
	a.x = sx,a.y = sy;
	wan[sx][sy] = -1;
	queue<node> q;
	q.push(a);
	while (!q.empty()){
		tmp = q.front();
		q.pop();
		if (tmp.x == ex && tmp.y == ey && wan[tmp.x][tmp.y] <= k){
			printf("yes\n");
			return;
		}
		for (int i = 0; i < 4; i++){
			a.x = tmp.x + dx[i];
			a.y = tmp.y + dy[i];
			while (a.x >= 0 && a.x < r && a.y >= 0 && a.y < c){
				if (map[a.x][a.y] == ‘*‘)
					break;
				if (wan[a.x][a.y] < wan[tmp.x][tmp.y]+1)
					break;
				wan[a.x][a.y] = wan[tmp.x][tmp.y] + 1;
				if (wan[a.x][a.y] > k)
					break;
				if (wan[a.x][a.y] == k && a.x != ex && a.y != ey)
					break;
				q.push(a);
				a.x += dx[i];
				a.y += dy[i];
			}
		}
	}
	printf("no\n");
}

int main(){
	int t;
	scanf("%d",&t);
	while (t--){
		scanf("%d%d",&r,&c);
		for (int i = 0; i < r; i++)
			scanf("%s",map[i]);
		scanf("%d%d%d%d%d",&k,&sy,&sx,&ey,&ex);
		sx--,sy--,ex--,ey--;
		bfs();
	}
	return 0;
}

HDU - 1728 逃离迷宫,布布扣,bubuko.com

HDU - 1728 逃离迷宫

原文：http://blog.csdn.net/u011345136/article/details/21469445