社区讨论
站外题求助
学术版参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m62clpt8
- 此快照首次捕获于
- 2025/01/18 23:33 去年
- 此快照最后确认于
- 2025/11/04 11:20 4 个月前
题面
代码:
CPP代码:
#include <bits/stdc++.h>
using namespace std;
int sx,sy,ex,ey,minn,apple;
char c[805][805];
int n,m;
int tot,bzx[805],bzy[805];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
int ansa[805][805];
bool vis[805][805];
struct node{
int x,y,step;
};
void banana()
{
queue<node>q;
q.push((node){sx,sy,0});
while(!q.empty()){
node now=q.front();
q.pop();
if(now.x<1||now.y<1||now.x>n||now.y>m) continue;
if(c[now.x][now.y]=='1'||c[now.x][now.y]=='3') continue;
if(vis[now.x][now.y]==1) continue;
vis[now.x][now.y]=1;
ansa[now.x][now.y]=now.step;
for(int i=1;i<=4;i++){
q.push((node){now.x+dx[i],now.y+dy[i],now.step+1});
}
}
}
void china()
{
memset(vis,0,sizeof(vis));
queue<node>q;
q.push((node){ex,ey,1});
while(!q.empty()){
node now=q.front();
q.pop();
if(now.x<1||now.y<1||now.x>n||now.y>m) continue;
if(c[now.x][now.y]=='1') continue;
if(vis[now.x][now.y]==1) continue;
vis[now.x][now.y]=1;
ansa[now.x][now.y]+=now.step;
for(int i=1;i<=4;i++){
q.push((node){now.x+dx[i],now.y+dy[i],now.step+1});
}
}
}
signed main()
{
ios::sync_with_stdio();
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c[i][j];
if(c[i][j]=='3')
{
ex=i;
ey=j;
}
if(c[i][j]=='2')
{
sx=i;
sy=j;
}
if(c[i][j]=='4')
{
bzx[++tot]=i;
bzy[tot]=j;
}
}
}
banana();
china();
apple=805*805;
for(int i=1;i<=tot;i++){
if(!vis[bzx[i]][bzy[i]]) continue;
apple=min(apple,ansa[bzx[i]][bzy[i]]-1);
// cout<<ansa[bzx[i]][bzy[i]]<<"\n";
}
cout<<apple;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...