求调
查看原帖
求调
1302823
sto_DFS_orz楼主2024/3/8 21:51
#include<bits/stdc++.h>
#define F(l,r,i) for(i=l;i<=r;i++)
#define ll long long
#define M 2005
#define inf 0x3f
using namespace std;
int n,m,sx,sy,ex,ey;
int dis[M][M],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
char a[M][M],f[4]={'v','^','>','<'};
struct node{
	int x,y;
}pre[M][M];
deque<node> dq; 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='x')
				ex=i,ey=j;
			if(a[i][j]=='o')
				sx=i,sy=j;
		}
	memset(dis,inf,sizeof dis);
	dq.push_back({sx,sy});
	dis[sx][sy]=0;
	while(!dq.empty()){
		node u=dq.front();
		dq.front();
		if(u.x==ex&&u.y==ey) continue;
		if(dis[u.x][u.y]>=dis[ex][ey]) continue;
		for(int i=0;i<4;i++){
			int vx=u.x+dx[i],vy=u.y+dy[i];
			if(vx<1||vx>n||vy<1||vy>m) continue;
			int w=(a[u.x][u.y]==f[i]||a[u.x][u.y]=='o');
			if(dis[vx][vy]>dis[u.x][u.y]+w){
				dis[vx][vy]=dis[u.x][u.y]+w;
				pre[vx][vy]=u;
				if(w==0) dq.push_front({vx,vy});
				else dq.push_back({vx,vy});
			}
		}
	}
	node last=pre[ex][ey],now=node{ex,ey};
	while(last.x!=sx||last.y!=sy){
		if(last.x==now.x+1)
			a[last.x][last.y]='^';
		if(last.x==now.x-1)
			a[last.x][last.y]='v';
		if(last.x==now.y+1)
			a[last.x][last.y]='<';
		if(last.x==now.x-1)
			a[last.x][last.y]='>';
		now=last;
		last=node{pre[last.x][last.y].x,pre[last.x][last.y].y};
	}
	cout<<dis[ex][ey]<<'\n';
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) cout<<a[i][j]<<' ';
		cout<<'\n';
	}
	return 0;
}
2024/3/8 21:51
加载中...