想问为啥拿不了70,虽然距离是暴力
查看原帖
想问为啥拿不了70,虽然距离是暴力
1073641
Birdly2楼主2023/10/17 21:56
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
char mapp[N][N];
int jto[N][N];
bool vis[N][N];
int fx[4] = {1,-1,0,0};
int fy[4] = {0,0,1,-1};
int nx,ny,vx,vy,tot;
int n,m,ans = INT_MAX;
struct tree{
	int x,y;
}tr[N * N];
struct add{
	int x,y,w;
};
int ju(int x1,int y1,int x2,int y2){
    return abs(x1 - x2) + abs(y1 - y2);
}
void intt(){
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			for(int k = 1;k <= tot;k++){
				int tmp = ju(i,j,tr[k].x,tr[k].y);
				jto[i][j] = min(jto[i][j],tmp);
			}
		}
	}
}
void bfs(){
	queue<add>q;
	q.push((add){nx,ny,jto[nx][ny]});
	vis[nx][ny] = 1;
	while(!q.empty()){
		add now = q.front();
		q.pop();
		int x1 = now.x ,y1 = now.y;
		if(x1 == vx && y1 == vy){
			ans = min(ans,now.w);
		}
		for(int i = 0;i < 4;i++){
			int tmp1 = x1 + fx[i],tmp2 = y1 + fy[i];
			if(!vis[tmp1][tmp2] && 1 <= tmp1 && tmp1 <= n && 1<=tmp2 && tmp2<=m){
				int tmp = min(now.w,jto[tmp1][tmp2]);
				q.push((add){tmp1,tmp2,tmp});
				vis[tmp1][tmp2] = 1;
			}
		}
	}
	return ;
}
int main(){
	memset(jto,0x3f,sizeof(jto));
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			cin >> mapp[i][j]; 
			char tmp = mapp[i][j];
			if(tmp == 'V'){
				nx = i,ny = j;
			}
			else if(tmp == 'J'){
				vx = i,vy = j;
			}
			else if(tmp == '+'){
				tot ++;
				tr[tot].x = i;
				tr[tot].y = j;
			}
		}
	}
	
	//cout << nx << " " << ny << "\n" << vx << " " << vy ;
	intt();
	bfs();
	/*for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			cout << jto[i][j] << " ";
		}
		puts("");
	}*/
	cout << ans;
	return 0;
}
2023/10/17 21:56
加载中...