题目描述(ID:12032)

标题: 解救小哈
详情: 有一天，小哈一个去玩迷宫。但是方向感很不好的小哈很快就迷路了。小哼得知后便立即去解救无助的小哈。小哼当然是有备而来，已经弄清楚了迷宫地图，现在小哼要以最快速度去解救小哈。问题就此开始了……
　　迷宫由n行m列的单元格组成，每个单元格要么是空地，要么是障碍物。你的任务是帮助小哼找到一条从迷宫的起点到小哈所在位置的最短路径，注意障碍物是不能走的，当然也不能走到迷宫之外。n和m都小于等于100。
输入格式: 
第一行有两个数N M。N表示迷宫的行，M表示迷宫的列。接来下来N行M列为迷宫，0表示空地，1表示障碍物。最后一行4个数，前两个数为迷宫入口的x和y坐标。后两个为小哈的x和y坐标。
输出格式: 
一个整数表示小哼到小哈的最短步数。如果不能解救小哈则输出No Way!
提示: RQNOJ 34紧急援救
195校园迷宫
样例:

输入

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3

输出

7

输入

3 3
1 1 1 
0 1 0 
0 1 0 
2 1 3 3

输出

No Way!

思路：

经典的DFS。


代码：

//DFS做法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int minn=99999999;
int n,m,targetx,targety;
int a[101][101],book[101][101];

void dfs(int x,int y,int step)
{
	int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
	int dx,dy,k;
	if(x==targetx&&y==targety)
	{
		if(step<minn)
		minn=step;
		return ;
	}
	
	for(int k=0;k<4;k++)
	{
		dx=x+dir[k][0];
		dy=y+dir[k][1];
		if(dx<1||dx>n||dy<1||dy>m)continue;
		if(a[dx][dy]==0&&book[dx][dy]==0)
		{
			book[dx][dy]=1;
			dfs(dx,dy,step+1);
			book[dx][dy]=0;
	    }
	}
	return;
}


int main()
{
	freopen("in.txt","r",stdin);
    int startx,starty;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
	       for(int j=1;j<=m;j++)
	         scanf("%d",&a[i][j]);
	    scanf("%d%d%d%d",&startx,&starty,&targetx,&targety);
	    
	    book[startx][starty]=1;
	    dfs(startx,starty,0);
	    
	    if(minn==99999999)printf("No Way!\n");
	    else printf("%d\n",minn);	
    }

    return 0;
} 




//BFS模版
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
const int INF=100000000; 
int n,m;
int a[101][101],d[101][101];
int sx,sy,gx,gy;  //起点和终点坐标 
typedef pair<int,int> P;

int bfs(){
	queue<P> que;
	//初始化所有位置 
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)d[i][j]=INF;
	//将起点加入队列 
	que.push(P(sx,sy));
	d[sx][sy]=0;	
	
	int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};	
	
	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],ny=p.second+dy[i];
			
			if(nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]!=1&&d[nx][ny]==INF){
				que.push(P(nx,ny));
				d[nx][ny]=d[p.first][p.second]+1;
			}
		}
	} 
	return d[gx][gy];	
}


int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	scanf("%d%d%d%d",&sx,&sy,&gx,&gy);  
	sx--;sy--;gx--;gy--;
	int res=bfs();
	if(res=100000000)puts("No Way!");
	else 	printf("%d\n",res);
	return 0;	
}