社区讨论

蒟蒻稀里糊涂地AC了，求dalao解答

yyangshenyu2
P5195[USACO05DEC] Knights of Ni S参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@miihp29w
此快照首次捕获于
2025/11/28 14:36
3 个月前
此快照最后确认于
2025/11/29 14:45
3 个月前
查看原帖
思路：分别从贝西和骑士出发，找到每个灌木丛的距离，再枚举每个灌木丛的双向距离
蒟蒻在AC后才发现题目中的这句话：在没有找到灌木之前，贝茜不能通过骑士们所在的那个区域。 可是我没有在代码中维护这个信息，是不是数据太水了貌似玄学
这是我的60WA代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;//贝西，knight骑士，shrub灌木
int p[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,bx,by,kx,ky,g[N][N],dis1[N][N],dis2[N][N],ans=0x3f3f3f3f;
vector<pair<int,int>>sh;
queue<pair<int,int>>q;
bool vis[N][N];
bool bou(int x,int y){
	return x>=1&&y>=1&&x<=n&&y<=m&&vis[x][y]==0&&g[x][y]!=1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]==2)bx=i,by=j;
			else if(g[i][j]==3)kx=i,ky=j;
			else if(g[i][j]==4)sh.push_back({i,j});
		}
	}
	q.push({bx,by});
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop();if(vis[x][y])continue;vis[x][y]=1;
		for(int i=0;i<4;i++){
			int x1=x+p[i][0],y1=y+p[i][1];
			if(bou(x1,y1)){
				dis1[x1][y1]=dis1[x][y]+1;
				q.push({x1,y1});
			}
		}
	}
	while(!q.empty())q.pop();
	memset(vis,0,sizeof(vis));
	q.push({kx,ky});
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop();if(vis[x][y])continue;vis[x][y]=1;
		for(int i=0;i<4;i++){
			int x1=x+p[i][0],y1=y+p[i][1];
			if(bou(x1,y1)){
				dis2[x1][y1]=dis2[x][y]+1;
				q.push({x1,y1});
			}
		}
	}
	for(auto [x,y]:sh)
		ans=min(ans,dis1[x][y]+dis2[x][y]);
	cout<<ans;
	return 0;
}
这是我的AC代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;//贝西，knight骑士，shrub灌木
int p[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,bx,by,kx,ky,g[N][N],dis1[N][N],dis2[N][N],ans=0x3f3f3f3f;
vector<pair<int,int>>sh;
queue<pair<int,int>>q;
bool vis[N][N];
bool bou(int x,int y){
	return x>=1&&y>=1&&x<=n&&y<=m&&vis[x][y]==0&&g[x][y]!=1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//	freopen("P5195_2.in","r",stdin);
	cin>>m>>n;
//	cout<<n<<' '<<m<<'\n';
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
//			cout<<g[i][j]<<' ';
			if(g[i][j]==2)bx=i,by=j;
			else if(g[i][j]==3)kx=i,ky=j;
			else if(g[i][j]==4)sh.push_back({i,j});
		}
//		cout<<'\n';
	}
//	cout<<'\n'<<bx<<' '<<by<<' '<<kx<<' '<<ky<<'\n';
	q.push({bx,by});
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop();if(vis[x][y])continue;vis[x][y]=1;
		for(int i=0;i<4;i++){
			int x1=x+p[i][0],y1=y+p[i][1];
			if(bou(x1,y1)){
				dis1[x1][y1]=dis1[x][y]+1;
				q.push({x1,y1});
			}
		}
	}
	while(!q.empty())q.pop();
	memset(vis,0,sizeof(vis));
	q.push({kx,ky});
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop();if(vis[x][y])continue;vis[x][y]=1;
		for(int i=0;i<4;i++){
			int x1=x+p[i][0],y1=y+p[i][1];
			if(bou(x1,y1)){
				dis2[x1][y1]=dis2[x][y]+1;
				q.push({x1,y1});
			}
		}
	}
	for(auto [x,y]:sh){
		if(dis1[x][y]!=0&&dis2[x][y]!=0)
			ans=min(ans,dis1[x][y]+dis2[x][y]);
//		cout<<x<<' '<<y<<' '<<dis1[x][y]<<' '<<dis2[x][y]<<'\n';
	}
	cout<<ans;
	return 0;
}
/*
15 15
4 1 1 0 1 1 0 0 0 0 1 0 0 0 0
1 0 1 0 0 0 0 1 0 1 0 1 1 1 0
0 1 0 4 1 0 0 0 0 1 1 1 1 0 0
0 0 0 1 0 0 0 1 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 4 1 0 0 0 0 1
0 0 0 4 1 1 1 1 0 1 1 0 1 1 1
0 0 0 1 1 1 1 0 1 1 0 1 0 1 1
0 0 0 0 0 1 1 1 0 1 0 1 0 0 0
0 0 1 1 0 0 0 0 1 0 0 0 0 1 4
1 0 0 0 1 0 1 0 0 0 0 0 0 1 0
4 1 1 0 0 0 0 0 0 0 0 1 0 1 1
1 0 0 1 1 0 0 1 0 1 0 4 0 1 0
1 0 1 0 0 0 1 0 0 0 0 0 4 0 0
4 0 1 0 0 1 0 0 4 0 0 0 0 0 0
1 1 0 1 1 0 0 0 0 0 0 2 0 3 0
*/
60WA掉后，下载样例看到输出发现
CPP
1 1 0 0
3 4 22 24
5 9 25 27
6 4 19 21
9 15 11 11
11 1 0 0
12 12 3 5
13 13 3 3
14 1 0 0
14 9 4 6
0
很疑惑为什么会有三个点的距离是0，以及为什么没有维护上面的所说的题目信息就能AC，百思不得其解（其实快困死了），于是我稀里糊涂地加了个特判就AC了，求dalao解答

回复

共 4 条回复，欢迎继续交流。

正在加载回复...