#include<bits/stdc++.h>
using namespace std;
typedef pair<int,pair<int,int> > PII;
const int N=1e3+10;
struct node
{
	int x,y;
}st,ed,a[N][N],last[10];
bool t[10],g[N][N];
int v[N][N],dis[N][N];
priority_queue<PII,vector<PII>,greater<PII> >Q;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		for(int j=1;j<=m;j++)
		{
			if(s[j-1]=='#')
			{
				v[i][j]=1;
			}
			if('1'<=s[j-1]&&s[j-1]<='9')
			{
				int k=s[j-1]-'0';
				if(t[k])
				{
					int x=last[k].x,y=last[k].y;
					a[x][y].x=i;
					a[x][y].y=j;
					a[i][j].x=x;
					a[i][j].y=y;
					v[x][y]=2;
					v[i][j]=2;
				}
				else
				{
					last[k].x=i;
					last[k].y=j;
					t[k]=1;
				}
			}
			if(s[j-1]=='S')
			{
				st.x=i;
				st.y=j;
			}
			if(s[j-1]=='E')
			{
				ed.x=i;
				ed.y=j;
			}
		}
	}
	memset(dis,0x3f,sizeof(dis));
	dis[st.x][st.y]=0;
	Q.push({0,{st.x,st.y}});
	while(Q.size())
	{
		auto I=Q.top();
		Q.pop();
		int x=I.second.first,y=I.second.second;
		if(g[x][y])
		{
			continue;
		}
		g[x][y]=1;
		for(int i=1;;i++)
		{
			int xx=x,yy=y+i;
			if(yy>m||dis[xx][yy]<dis[x][y]+1||v[xx][yy]==1)
			{
				break;
			}
			else
			{
				dis[xx][yy]=dis[x][y]+1;
				Q.push({dis[xx][yy],{xx,yy}});
				if(v[xx][yy]==2)
				{
					int xxx=a[xx][yy].x,yyy=a[xx][yy].y;
					if(dis[xxx][yyy]>dis[x][y]+1)
					{
						dis[xxx][yyy]=dis[x][y]+1;
						Q.push({dis[xxx][yyy],{xxx,yyy}});
					}
				}
			}
		}
		for(int i=1;;i++)
		{
			int xx=x,yy=y-i;
			if(yy<=0||dis[xx][yy]<dis[x][y]+1||v[xx][yy]==1)
			{
				break;
			}
			else
			{
				dis[xx][yy]=dis[x][y]+1;
				Q.push({dis[xx][yy],{xx,yy}});
				if(v[xx][yy]==2)
				{
					int xxx=a[xx][yy].x,yyy=a[xx][yy].y;
					if(dis[xxx][yyy]>dis[x][y]+1)
					{
						dis[xxx][yyy]=dis[x][y]+1;
						Q.push({dis[xxx][yyy],{xxx,yyy}});
					}
				}
			}
		}
		for(int i=1;;i++)
		{
			int xx=x+i,yy=y;
			if(xx>n||dis[xx][yy]<dis[x][y]+1||v[xx][yy]==1)
			{
				break;
			}
			else
			{
				dis[xx][yy]=dis[x][y]+1;
				Q.push({dis[xx][yy],{xx,yy}});
				if(v[xx][yy]==2)
				{
					int xxx=a[xx][yy].x,yyy=a[xx][yy].y;
					if(dis[xxx][yyy]>dis[x][y]+1)
					{
						dis[xxx][yyy]=dis[x][y]+1;
						Q.push({dis[xxx][yyy],{xxx,yyy}});
					}
				}
			}
		}
		for(int i=1;;i++)
		{
			int xx=x-i,yy=y;
			if(xx<=0||dis[xx][yy]<dis[x][y]+1||v[xx][yy]==1)
			{
				break;
			}
			else
			{
				dis[xx][yy]=dis[x][y]+1;
				Q.push({dis[xx][yy],{xx,yy}});
				if(v[xx][yy]==2)
				{
					int xxx=a[xx][yy].x,yyy=a[xx][yy].y;
					if(dis[xxx][yyy]>dis[x][y]+1)
					{
						dis[xxx][yyy]=dis[x][y]+1;
						Q.push({dis[xxx][yyy],{xxx,yyy}});
					}
				}
			}
		}
		for(int i=1;;i++)
		{
			int xx=x+i,yy=y+i;
			if(yy>m||xx>n||dis[xx][yy]<dis[x][y]+1||v[xx][yy]==1)
			{
				break;
			}
			else
			{
				dis[xx][yy]=dis[x][y]+1;
				Q.push({dis[xx][yy],{xx,yy}});
				if(v[xx][yy]==2)
				{
					int xxx=a[xx][yy].x,yyy=a[xx][yy].y;
					if(dis[xxx][yyy]>dis[x][y]+1)
					{
						dis[xxx][yyy]=dis[x][y]+1;
						Q.push({dis[xxx][yyy],{xxx,yyy}});
					}
				}
			}
		}
		for(int i=1;;i++)
		{
			int xx=x-i,yy=y-i;
			if(xx<=0||yy<=0||dis[xx][yy]<dis[x][y]+1||v[xx][yy]==1)
			{
				break;
			}
			else
			{
				dis[xx][yy]=dis[x][y]+1;
				Q.push({dis[xx][yy],{xx,yy}});
				if(v[xx][yy]==2)
				{
					int xxx=a[xx][yy].x,yyy=a[xx][yy].y;
					if(dis[xxx][yyy]>dis[x][y]+1)
					{
						dis[xxx][yyy]=dis[x][y]+1;
						Q.push({dis[xxx][yyy],{xxx,yyy}});
					}
				}
			}
		}
		for(int i=1;;i++)
		{
			int xx=x+i,yy=y-i;
			if(xx>n||yy<=0||dis[xx][yy]<dis[x][y]+1||v[xx][yy]==1)
			{
				break;
			}
			else
			{
				dis[xx][yy]=dis[x][y]+1;
				Q.push({dis[xx][yy],{xx,yy}});
				if(v[xx][yy]==2)
				{
					int xxx=a[xx][yy].x,yyy=a[xx][yy].y;
					if(dis[xxx][yyy]>dis[x][y]+1)
					{
						dis[xxx][yyy]=dis[x][y]+1;
						Q.push({dis[xxx][yyy],{xxx,yyy}});
					}
				}
			}
		}
		for(int i=1;;i++)
		{
			int xx=x-i,yy=y+i;
			if(xx<=0||yy>m||dis[xx][yy]<dis[x][y]+1||v[xx][yy]==1)
			{
				break;
			}
			else
			{
				dis[xx][yy]=dis[x][y]+1;
				Q.push({dis[xx][yy],{xx,yy}});
				if(v[xx][yy]==2)
				{
					int xxx=a[xx][yy].x,yyy=a[xx][yy].y;
					if(dis[xxx][yyy]>dis[x][y]+1)
					{
						dis[xxx][yyy]=dis[x][y]+1;
						Q.push({dis[xxx][yyy],{xxx,yyy}});
					}
				}
			}
		}
	}
	if(dis[ed.x][ed.y]==0x3f3f3f3f)
	{
		cout<<"-1";
		return 0;
	}
	cout<<dis[ed.x][ed.y];
	return 0;
}

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

思路

很容易想到 BFS，特殊点在于有 $8$ 个方向，且每个方向要跑到边界或障碍物，遇到走过的格子（即 $vis_{i,j} = 1$）也不要 break！continue 就行了，具体见代码 $49$ 行。

代码如下↓

#include<bits/stdc++.h>
using namespace std;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, -1, 1, -1, 1};

int n, m, ans = 0x3f3f3f3f;
char c[1005][1005];
struct node
{
	int x, y, cnt;
}; queue<node> q;
bool vis[1005][1005];
vector<node> v[10];

bool chk(int x, int y)
{
	if(x > n || y > m || x < 1 || y < 1) return false;
	if(c[x][y] == '#') return false;
	return true;
}

int main()
{
	cin >> n >> m; cin.get();
	for(int i = 1; i <= n; i++) 
	{
		scanf("%s", c[i] + 1);
		for(int j = 1; j <= m; j++)
		{
			if(c[i][j] == 'S') q.push({i, j, 0}), vis[i][j] = true;
			if(c[i][j] >= '0' && c[i][j] <= '9')
				v[(c[i][j] - '0')].push_back({i, j, -1});
		}
	}
	while(!q.empty())
	{
		node u = q.front(); q.pop();
		if(c[u.x][u.y] == 'E')
		{
			ans = min(ans, u.cnt);
			break;
		}
		for(int i = 0; i < 8; i++)
		{
			int t = 1;
			while(true)
			{
				int nx = u.x + t * dx[i], ny = u.y + t * dy[i]; t++;
				if(vis[nx][ny]) continue; if(!chk(nx, ny)) break;
				vis[nx][ny] = true; q.push({nx, ny, u.cnt + 1});
				if(c[nx][ny] >= '1' && c[nx][ny] <= '9')
				{
					int tmp = c[nx][ny] - '0';
					for(auto k : v[tmp])
						if(k.x != nx || k.y != ny)
						{
							if(vis[k.x][k.y]) continue;
							q.push({k.x, k.y, u.cnt + 1});
							vis[k.x][k.y] = true;
						}
				}
			}
		}
	}
	if(ans != 0x3f3f3f3f) cout << ans << endl;
	else cout << -1 << endl;
	return 0;
}