Oliver的救援(bfs)

Oliver的救援

*Description

在你的帮助下，Oliver终于追到小X了，可有一天，坏人把小X抓走了。这正是Oliver英雄救美的时候。所以，Oliver又找到哆啦A梦，借了一个机器，机器显示出一幅方格地图，它告诉Oliver哪里能走，哪里不能走,。并且Oliver在这个地图的(x,y)，而小X在(x1,y1)。时间紧急，Oliver想知道，最少要走多少个格子,才能找到小X。（只能直走）。

Input

共N+2行，第一行为N，以下N行N列0-1矩阵，1表示不能通过,0表示可以通过(左上角和右下角为0). N<1000.
第N+2行，x,y,x1,y1;
Output

共一个数，为最少的走的格子数.

Sample Input

5
0 1 1 1 1
0 0 1 1 1
1 0 0 0 1
1 1 1 0 1
1 1 1 0 0
5 5 1 1

Sample Output

9
**分析：模板题，我就不说了！！哈哈 **

code：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1000;
const int dx[5]={0,0,-1,0,1};
const int dy[5]={0,-1,0,1,0};
int a[N+1][N+1];
int fa[N*N+1];
int st[N*N+1][4];
int px,py,qx,qy,n,last;
void bfs()
{
	int head=0,tail=1;
	st[1][1]=px; st[1][2]=py; //初始化
	do
	{
		head++;
		for(int k=1;k<=4;k++)  //当前节点向四个方向扩展
		{
			int nx=st[head][1]+dx[k],ny=st[head][2]+dy[k];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&a[nx][ny]==0)  //判断条件
			{
				//入队
				tail++;
				st[tail][1]=nx;
    			st[tail][2]=ny;
    			st[tail][3]=st[head][3]+1;
				a[nx][ny]=1;
				if(st[tail][1]==qx&&st[tail][2]==qy)
				{
					cout<<st[tail][3]<<endl;
					return ;
				}
			}
		}
	}while(head<tail);
}
int main() 
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		char b;
		cin>>b;
	   	a[i][j]=b-'0';   （注意：这题输入是用字符输入！~~因此害我检查了二十分钟，巨坑 ~~ ） o(╥﹏╥)o	
	}
	scanf("%d%d%d%d",&px,&py,&qx,&qy);
	a[px][py]=1;
    bfs();
	return 0;
}

谢谢！