专栏文章

题解：P14469 [COCI 2025/2026 #1] 皇后 / Kraljica

IInnitTimmer_
P14469题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minazeei
此快照首次捕获于
2025/12/01 23:27
3 个月前
此快照最后确认于
2025/12/01 23:27
3 个月前
查看原文
首先这道题先考虑 bfs 做法，我们发现对于数字之间的传送是不需要任何花费的，所以可以将他们的边权设为 00，然而对于普通的点之间的边权就是 11，直接使用 0101 BFS 即可通过。
因为我们第一次 bfs 到一个点就是最优答案，所以每个点规定经过一次，时间复杂度 O(n2)O(n^2)。
代码比较难写，注意一些细节。
CPP
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
bool Test_MLE_start;
constexpr int N=1001;
int _=1,n,m,sx,sy,fx,fy,x[10][2],y[10][2],dp[N][N];
char s[N][N];bool vis[N][N];
struct node {int x,y;};
deque<node> q;
inline int reads() {
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) {
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
	return x*f;
}
inline void files() {
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr() {
//	Don't forget!

}
void bfs(int sx,int sy) {
	memset(dp,0x3f,sizeof(dp));
	q.push_back(node {sx,sy});
	dp[sx][sy]=0;
	while(!q.empty()) {
		int idx=q.front().x,idy=q.front().y;
		q.pop_front();
		if(vis[idx][idy]) continue;
		vis[idx][idy]=1;
		for(int x=idx+1; x<=n; x++) {
			int y=idy;
			if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
			if(dp[x][y]>dp[idx][idy]+1){
				dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
				q.push_back(node {x,y});
			}
		}
		for(int x=idx-1; x>=1; x--) {
			int y=idy;
			if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
			if(dp[x][y]>dp[idx][idy]+1){
				dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
				q.push_back(node {x,y});
			}
		}
		for(int y=idy+1; y<=m; y++) {
			int x=idx;
			if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
			if(dp[x][y]>dp[idx][idy]+1){
				dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
				q.push_back(node {x,y});
			}
		}
		for(int y=idy-1; y>=1; y--) {
			int x=idx;
			if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
			if(dp[x][y]>dp[idx][idy]+1){
				dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
				q.push_back(node {x,y});
			}
		}
		for(int x=idx+1,y=idy+1; x<=n,y<=m; x++,y++) {
			if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
			if(dp[x][y]>dp[idx][idy]+1){
				dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
				q.push_back(node {x,y});
			}
		}
		for(int x=idx+1,y=idy-1; x<=n,y>=1; x++,y--) {
			if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
			if(dp[x][y]>dp[idx][idy]+1){
				dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
				q.push_back(node {x,y});
			}
		}
		for(int x=idx-1,y=idy+1; x>=1,y<=m; x--,y++) {
			if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
			if(dp[x][y]>dp[idx][idy]+1){
				dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
				q.push_back(node {x,y});
			}
		}
		for(int x=idx-1,y=idy-1; x>=1,y>=1; x--,y--) {
			if(x<1||x>n||y<1||y>m||s[x][y]=='#') break;
			if(dp[x][y]>dp[idx][idy]+1){
				dp[x][y]=min(dp[x][y],dp[idx][idy]+1);
				q.push_back(node {x,y});
			}
		}
		if(isdigit(s[idx][idy])) {
			int p=s[idx][idy]-'0',px,py;
			if(idx==x[p][0]&&idy==y[p][0]) px=x[p][1],py=y[p][1];
			else px=x[p][0],py=y[p][0];
			dp[px][py]=min(dp[px][py],dp[idx][idy]);
			q.push_front(node {px,py});
		}
	}
}
bool Test_MLE_end;
signed main() {
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--) {
		clr();
		n=reads(),m=reads();
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++) {
				cin>>s[i][j];
				if(s[i][j]=='S') sx=i,sy=j;
				else if(s[i][j]=='E') fx=i,fy=j;
				else if(isdigit(s[i][j])) {
					int p=s[i][j]-'0';
					if(!x[p][0]) x[p][0]=i;
					else x[p][1]=i;
					if(!y[p][0]) y[p][0]=j;
					else y[p][1]=j;
				}
			}
		}bfs(sx,sy);
		if(dp[fx][fy]==0x3f3f3f3f) puts("-1");
		else printf("%d\n",dp[fx][fy]);
	}
	return 0;
}
/*
5 5
S##..
##...
..#..
.....
.#..E
*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...