题目背景：
《爱与愁的故事第三弹·shopping》最终章。
题目描述：
爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在x1,y1处，车站在x2,y2处。现在给出一个n×n（n<=1000）的地图，0表示马路，1表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（a[i][j]距离为1）。你能帮他解决吗？
输入格式：
第1行：一个数 n
第2行~第n+1行：整个地图描述（0表示马路，1表示店铺，注意两个数之间没有空格）
第n+2行：四个数 x1,y1,x2,y2
输出格式：
只有1行：最短到达目的地距离
样例输入：
3
001
101
100
1 1 3 3
样例输出：
4
说明/提示：
20%数据：n<=100
100%数据：n<=1000
AC Code：
#include<bits/stdc++.h> using namespace std; #define N 1001 char s[N][N];//存入地图 bool vis[N][N];//标记数组 int n,sx,sy,ex,ey,head,tail; int dx[]={0,0,1,-1};//方向数组 int dy[]={1,-1,0,0}; struct node {//定义结构体用来模拟队列 int x,y,step; }q[N*N]; bool judge(int x,int y) {//不越界，不是店铺，这个点没有走过 if(x>=1&&x<=n&&y>=1&&y<=n&&s[x][y]!='1'&&vis[x][y]==false) { return true; } return false; } int main() { memset(vis,false,sizeof(vis));//标记数组清零 scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf(" %c",&s[i][j]);//%前面的空格确保输入完整 } } scanf("%d %d %d %d",&sx,&sy,&ex,&ey); vis[sx][sy]=true;//标记起点 head=tail=1;//初始化队头队尾 q[head].x=sx;//起点坐标入队 q[head].y=sy; q[head].step=0;//步数初始为0 tail++;//起点入队之后，队尾向后移动一格 while(head<tail) { for(int i=0;i<4;i++) {//四个方向搜索 int tx=q[head].x+dx[i]; int ty=q[head].y+dy[i]; if(tx==ex&&ty==ey) {//走到终点 printf("%d\n",q[head].step+1);//步数=上个点步数+1 return 0; } if(judge(tx,ty)) {//合法判断 vis[tx][ty]=true;//标记这个点 q[tail].x=tx;//新的点入队 q[tail].y=ty; q[tail].step=q[head].step+1;//步数+1 tail++;//队尾后移 } } head++;//处理完一个点，队头向后移一格，搜索下一个点 } return 0; }
