离开中山路
题目背景
《爱与愁的故事第三弹·shopping》最终章。
题目描述
爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在 x 1 , y 1 x_1,y_1 x1,y1 处，车站在 x 2 , y 2 x_2,y_2 x2,y2 处。现在给出一个 n × n ( n ≤ 1000 ) n \times n(n \le 1000) n×n(n≤1000) 的地图， 0 0 0 表示马路， 1 1 1 表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（每两个相邻坐标间距离为 1 1 1）。你能帮他解决吗？
输入格式
第 1 1 1 行包含一个数 n n n。
第 2 2 2 行到第 n + 1 n+1 n+1 行：整个地图描述（ 0 0 0 表示马路， 1 1 1 表示店铺，注意两个数之间没有空格）。
第 n + 2 n+2 n+2 行：四个数 x 1 , y 1 , x 2 , y 2 x_1,y_1,x_2,y_2 x1,y1,x2,y2。
输出格式
只有 1 1 1 行，即最短到达目的地距离。
样例 #1
样例输入 #1
3
001
101
100
1 1 3 3
样例输出 #1
4
提示
对于 20 % 20\% 20% 数据，满足 1 ≤ n ≤ 100 1\leq n \le 100 1≤n≤100。
对于 100 % 100\% 100% 数据，满足 1 ≤ n ≤ 1000 1\leq n \le 1000 1≤n≤1000。
C++实现
#include
#include
int fx[4]={1,0,-1,0};
int fy[4]={0,1,0,-1};
char ma[1001][1001];
struct node{int x,y,c;}q[1100000];
int n;
void bfss(int stx,int sty,int enx,int eny){
int tou=1,wei=2;//接下来几句就是一般的搜索了
q[tou].x=stx;q[tou].y=sty;//第一步在起点开始
q[tou].c=0;//走到起点需要0步
while(tou!=wei){
for(int i=0;i<4;i++){
int xx=q[tou].x+fx[i];
int yy=q[tou].y+fy[i];
if(xxenx&&yyeny){printf(“%d”,q[tou].c+1);return;}
if(xx<1||xx>n||yy<1||yy>n||ma[xx][yy]==‘1’) continue;
ma[xx][yy]=‘1’;//走过了封路
q[wei].x=xx;//走下一步
q[wei].y=yy;//走下一步
q[wei].c=q[tou].c+1;//步数加一
wei++;//前进
}
tou++;//前进
}
}
int main(){
scanf(“%d”,&n);
for(int i=1;i<=n;i++) {
scanf(“%s”,ma[i]+1);
}
int sx,sy,ex,ey;scanf(“%d %d %d %d”,&sx,&sy,&ex,&ey);
ma[sx][sy]=1;//起点为1
bfss(sx,sy,ex,ey);//搜索
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
标签：信奥,int,wei,P1746,tou,ma,打卡,100,1000 From： https://blog.csdn.net/rogeliu/article/details/143659887