DFS,BFS

#include "bits/stdc++.h" #define int long long using namespace std; const int N=3e3+10; int n,m,sx,sy; char a[N][N]; int dist[N][N]; bool st[N][N]; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; struct nodep{ int px,py,pcnt; }; struct nodeq{ int qx1,qy1,qx2,qy2,qcnt; }; signed main() { ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m>>sx>>sy; memset(dist,-1,sizeof(dist)); queue<nodep>p; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>a[i][j]; if(a[i][j]=='@') p.push({i,j,0}); } while(!p.empty()) { nodep w=p.front(); p.pop(); int x=w.px; int y=w.py; int cnt=w.pcnt; if(dist[x][y]!=-1)//RRRRR continue; dist[x][y]=cnt; for(int i=0;i<4;i++) { int tx=x+dx[i]; int ty=y+dy[i]; if(tx<1||tx>n||ty<1||ty>m||dist[tx][ty]!=-1) continue; if(a[tx][ty]=='.') p.push({tx,ty,cnt+1}); } } queue<nodeq>q; q.push({sx,sy,sx,sy,0}); int ans=100000000000000; while(q.empty()==0) { nodeq ww=q.front(); q.pop(); int x1=ww.qx1; int y1=ww.qy1; int x2=ww.qx2; int y2=ww.qy2; int cnt=ww.qcnt; if(st[x1][y1]) continue; st[x1][y1]=true; for(int i=0;i<4;i++) { int ix=x1+dx[i]; int iy=y1+dy[i]; int jx=x2-dx[i]; int jy=y2-dy[i]; if(ix<1||ix>n||iy<1||iy>m||st[ix][iy]) continue; if(jx<1||jx>n||jy<1||jy>m) continue; if(a[ix][iy]=='@'&&a[jx][jy]!='#') ans=min(ans,cnt+1+dist[jx][jy]); if(a[ix][iy]=='.'&&a[jx][jy]=='.') q.push({ix,iy,jx,jy,cnt+1}); } } if(ans==100000000000000) ans=-1; cout<<ans<<'\n'; }
上一篇:深度学习实战96-GCN网络的架构以及GCN在股票领域的应用,给出了数据和核心代码实现


下一篇:如何在当前时刻采样上一拍的值?always_ff always-一、实现方式