关注
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;
int n;
int a[5100][5100];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int vis[5100][5100];
struct node
{
int x,y,dis;
node(){}
node(int xx,int yy,int ddis):x(xx),y(yy),dis(ddis){}
};
vector<node> ve;
int bfs()
{
queue<node> q0,q1;
ve.clear();
q0.push(node(0,0,0));
vis[0][0]=1;
while(1)
{
bool judge=false;
while(!q0.empty())
{
judge=true;
node z=q0.front();q0.pop();
if(z.x==n-1&&z.y==n-1) return z.dis;
for(int i=0;i<4;i++)
{
int nx=z.x+dir[i][0];
int ny=z.y+dir[i][1];
if(nx<0||nx>=n||ny<0||ny>=n) continue;
if(vis[nx][ny]) continue;
if(a[nx][ny]==0) q0.push(node(nx,ny,z.dis));
else q1.push(node(nx,ny,z.dis+1));
vis[nx][ny]=1;
}
}
if(!judge)
{
int sz=(int)ve.size();
for(int i=0;i<sz;i++)
{
q1.push(ve[i]);
vis[ve[i].x][ve[i].y]=1;
}
ve.clear();
}
while(!q1.empty())
{
node z=q1.front();q1.pop();
if(z.x==n-1&&z.y==n-1) return z.dis;
for(int i=0;i<4;i++)
{
int nx=z.x+dir[i][0];
int ny=z.y+dir[i][1];
if(nx<0||nx>=n||ny<0||ny>=n) continue;
if(vis[nx][ny]) continue;
if(a[nx][ny]==0)
{
q0.push(node(nx,ny,z.dis));
vis[nx][ny]=1;
}
else ve.push_back(node(nx,ny,z.dis+1));
}
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&a[i][j]);
memset(vis,0,sizeof(vis));
printf("%d\n",bfs());
}
return 0;
} 第三题
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
05-27 18:16
安阳师范学院 Java 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 聊聊这家公司值得去吗 #
229999次浏览 2164人参与
# 职场人,说说你的烦心事 #
8261次浏览 65人参与
# 你认为哪个岗位找工作最卷 #
9289次浏览 34人参与
# 职场上哪些事情令人讨厌 #
16520次浏览 81人参与
# 一人一个landing小技巧 #
78059次浏览 1112人参与
# 秋招最大的收获是什么? #
33773次浏览 296人参与
# kpi面有什么特征 #
29978次浏览 167人参与
# 大家每天通勤多久? #
41854次浏览 329人参与
# 小红书求职进展汇总 #
55998次浏览 483人参与
# 职场破防瞬间 #
234787次浏览 2125人参与
# 为了找工作你投递了多少公司? #
8099次浏览 105人参与
# 职场吐槽大会 #
204670次浏览 1628人参与
# tplink提前批进度交流 #
162543次浏览 1377人参与
# 许愿池 #
282998次浏览 2868人参与
# 机械制造岗投递时间线 #
22652次浏览 345人参与
# 通信硬件牛牛的实习日记 #
7066次浏览 65人参与
# 找工作前vs找工作后的心路变化 #
9539次浏览 101人参与
# 聊聊你的职场新体验 #
157232次浏览 1367人参与
# 经纬恒润求职进展汇总 #
118840次浏览 1027人参与
# 入职第一天,你准备什么时候下班 #
55485次浏览 351人参与