关注
#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-10 14:31
华南师范大学 Java 点赞 评论 收藏
分享
05-29 22:11
门头沟学院 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 考研对你找工作产生了哪些影响? #
6217次浏览 70人参与
# 打杂的实习你会去吗? #
109103次浏览 954人参与
# 聊聊这家公司值得去吗 #
240710次浏览 2244人参与
# 机械只有读研才有出路吗? #
20032次浏览 228人参与
# 你认为哪个岗位找工作最卷 #
17241次浏览 67人参与
# 面试被问第一学历差时该怎么回答 #
130944次浏览 823人参与
# 远程面试的尴尬瞬间 #
101163次浏览 830人参与
# 硬件人绝对不能踩的坑 #
61509次浏览 736人参与
# 工作中哪个瞬间让你想离职 #
24295次浏览 166人参与
# kpi面有什么特征 #
36471次浏览 266人参与
# 你有哪些缓解焦虑的方法? #
4176次浏览 146人参与
# 如何缓解入职前的焦虑 #
187479次浏览 1319人参与
# 职场人,说说你的烦心事 #
9189次浏览 83人参与
# 秋招最大的收获是什么? #
34317次浏览 302人参与
# 实习生应该准时下班吗 #
223685次浏览 1398人参与
# 职场上哪些事情令人讨厌 #
16992次浏览 86人参与
# 你今年的平均薪资是多少? #
126887次浏览 661人参与
# 为了找工作你投递了多少公司? #
12795次浏览 180人参与
# 运营/市场营销人的秋招现状 #
17381次浏览 189人参与
# 数字马力求职进展汇总 #
175443次浏览 1470人参与