问题 C: 1逃出城堡

时间限制: 1 Sec 内存限制: 128 MB 提交: 28 解决: 44

[命题人:luping]

题目描述 羊羊们选出的代表不负重望，击败了骄傲的Jack。Jack恼羞成怒，违反了原则要抓小羊，情况紧急，羊羊们必须找到一条最短的路径逃出Jack的城堡。Jack的城堡是一个n*m的矩形，里面有一些地方可以通过（用0表示），有一些地方则为墙或障碍物（用1表示），无法通过，小羊们处于（x，y）处，出口在（n，m）处。可小羊们无法立刻求到这条路径，这时，善良而伟大的Yyz出现了，他给了羊羊们城堡的地图和一台笔记本电脑。羊羊们要通过这来求出到出口的最短路径。

输入 第1行，两个正整数n，m（n，m≤500），表示城堡的长和宽。

第2~n+1行，每行n个数字（0和1），表示此处城堡地形。

第n+2行，两个正整数x，y（x，y均不超过n，m），表示小羊所处位置。

输出

一行，一个数，表示最短路径的长度。

样例输入

6 5

0 0 1 0 1

1 0 0 0 0

1 1 0 1 0

0 0 0 1 0

1 0 1 1 0

1 0 0 0 0

2 2

样例输出

7 代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,ii,ans,c,v,q[1000000],p[1000000],h[2001][2001]; 
int a[2000][2000]; 
int b[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
bool ff;
void bfs(int x,int y)
{
  int xx=0,yy=0,w=0,t=0,i=0;
  h[x][y]=0;
  q[1]=x; 
  p[1]=y;
  t=0;
  w=1;
  while (t<w)
    {
    	t++;
    	for (i=0;i<4;i++)
    	{
    		xx=q[t]+b[i][0];yy=p[t]+b[i][1];
    		if (h[xx][yy]>h[q[t]][p[t]]+1&&a[xx][yy]!=1) 
    		{
    			w++;
    			q[w]=xx;
				p[w]=yy;
				h[xx][yy]=h[q[t]][p[t]]+1;
				if (xx==c&&yy==v){printf("%d",h[xx][yy]);ff=true;return;}
			}
		}
	}	
	return;
}
int main()
{
	scanf("%d %d",&n,&m);
	for (i=1;i<=n;i++)
	  for (j=1;j<=m;j++)
		scanf("%d",&a[i][j]);
	for (i=1;i<=n;i++)
	  for (j=1;j<=m;j++)
	      h[i][j]=1e9;
	scanf("%d %d",&c,&v);
	bfs(n,m); 
	if (ff=false) printf("0");
return 0;
}