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

//# pragma GCC optimize("Ofast")
# include <bits/stdc++.h>
# define fr front
# define il inline
# define fir first
# define sec second
# define vec vector
# define it iterator
# define pb push_back
# define lb lower_bound
# define ub upper_bound
# define all(x) x.begin(), x.end()
# define mem(a, b) memset(a, b, sizeof(a))

# define lc (t[p].l)
# define rc (t[p].r)
# define ls(x) (x << 1)
# define rs(x) (x << 1 | 1)
# define lson ls(p), l, mid
# define rson rs(p), mid + 1, r

# define sqr(x) ((x) * (x))
# define bpc __builtin_popcount
# define lowbit(x) ((x) & (-(x)))
# define geti(x, i) (((x) >> (i)) & 1)
# define set1(x, i) ((x) | (1 << (i)))
# define set0(x, i) ((x) & (~(1 << (i))))

# define debug1(x) cerr << #x << " = " << x << " "
# define debug2(x) cerr << #x << " = " << x << "\n"
# define bug cerr << "--------------------------\n"

# define each1(i, x) for(auto (i) : (x))
# define each2(i, x) for(auto (&i) : (x))
# define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
# define pre(i, a, b) for(int i = (a); i >= (b); -- i)
# define G(i, h, u, ne) for(int i = (h[(u)]); i; i = (ne[(i)]))
# define reps(i, a, b, c) for(int i = (a); i <= (b); i += (c))
# define pres(i, a, b, c) for(int i = (a); i >= (b); i -= (c))
using namespace std;

using DB = double;
using LL = long long;
using LDB = long double;
using PII = pair<int, int>;
using ULL = unsigned long long;

const int N = 1e3 + 10;
const int INF1 = 0x3f3f3f3f, INF2 = INT_MAX;
const LL INF3 = (LL)1e18, INF4 = 0x3f3f3f3f3f3f3f3f, INF5 = LLONG_MAX;

int n, m, sx, sy, ex, ey, ans;
int vis[N][N][10];

char mp[N][N];

vec<PII> a[10];

int dx[10] = {0, 1, 1, 1, 0, 0, -1, -1, -1};
int dy[10] = {0, -1, 0, 1, -1, 1, -1, 0, 1};

struct node{
	int x, y, dir;
};

void calc(int num, int &x, int &y){//求出编号为num的传送门的相应出口 
	each2(tmp, a[num]){
		if(tmp.fir ^ x || tmp.sec ^ y){
			x = tmp.fir, y = tmp.sec;
			return;
		}
	}
}

void BFS(){
	mem(vis, 0x3f);
	rep(i, 0, 8) vis[sx][sy][i] = 0;
	deque<node> q;
	q.pb({sx, sy, 0});//起点没有方向 
	
	while(!q.empty()){
		int x = q.fr().x, y = q.fr().y, dir = q.fr().dir;
		q.pop_front();
		
		rep(i, 1, 8){
			int nx = x + dx[i], ny = y + dy[i];
			if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
			if(mp[nx][ny] == '#' || vis[nx][ny][i] <= vis[x][y][dir] + (dir != i)) continue;
			vis[nx][ny][i] = vis[x][y][dir] + (dir != i);
			if(dir ^ i) q.pb({nx, ny, i});
			else q.push_front({nx, ny, i});
		}
		
		if('1' <= mp[x][y] && mp[x][y] <= '9'){//传送门 
			int num = mp[x][y] - '0';
			int i = x, j = y;
			calc(num, i, j);
			if(vis[i][j][0] ^ INF1) continue;
			vis[i][j][0] = vis[x][y][dir];
			q.push_front({i, j, 0});//传送门出口方向设为0 
		}
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	ans = INF1;
	cin >> n >> m;
	
	rep(i, 1, n) cin >> mp[i] + 1;
	
	rep(i, 1, n){
		rep(j, 1, m){
			if(mp[i][j] == 'S') sx = i, sy = j;
			else if(mp[i][j] == 'E') ex = i, ey = j;
			else if(mp[i][j] != '#' && mp[i][j] != '.') a[mp[i][j] - '0'].pb({i, j});
		}
	}
	
	BFS();
	
	rep(i, 0, 8) ans = min(ans, vis[ex][ey][i]);
	
	if(ans ^ INF1) cout << ans;
	else cout << "-1";
	
	return 0;
}