提出 #70786809

---

ソースコード 拡げる

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
// from:左上下右
const int dxA[4] = { 0,1,-1,0 };
const int dyA[4] = { 1,0,0,-1 };
const int dzA[4] = { 0,1,2,3 };//どこから？

const int dxB[4] = { 1,0,0,-1 };
const int dyB[4] = { 0,1,-1,0 };
const int dzB[4] = { 1,0,3,2 };//どこから？

const int dxC[4] = { -1,0,0,1 };
const int dyC[4] = { 0,-1,1,0 };
const int dzC[4] = { 2,3,0,1 };//どこから？
void solve() {
	int h, w; cin >> h >> w;
	vector<string>s(h);
	rep(i, h)cin >> s[i];
	vector dp(h, vector(w, vector<int>(4, INF)));
	dp[0][0][0] = 0;
	deque<array<int, 3>>que;
	que.push_back({ 0,0,0 });
	int ans = INF;
	while (!que.empty()) {
		auto[x, y, t] = que.front();
		//cout << x << " " << y << " " << t << " " << dp[x][y][t] << endl;
		que.pop_front();
		{//A
			int nx = x + dxA[t];
			int ny = y + dyA[t];
			int nt = dzA[t];
			int add = s[x][y] == 'A' ? 0 : 1;
			if (nx == h - 1 && ny == w)chmin(ans, dp[x][y][t] + add);
			if (0 <= nx && nx < h && 0 <= ny && ny < w)
			{
				if (chmin(dp[nx][ny][nt], dp[x][y][t] + add)) {
					if (add == 0) {
						que.push_front({ nx,ny,nt });
					}
					else {
						que.push_back({ nx,ny,nt });
					}
				}
			}
		}
		{//B
			int nx = x + dxB[t];
			int ny = y + dyB[t];
			int nt = dzB[t];
			int add = s[x][y] == 'B' ? 0 : 1;
			if (nx == h - 1 && ny == w)chmin(ans, dp[x][y][t] + add);
			if (0 <= nx && nx < h && 0 <= ny && ny < w)
			{
				if (chmin(dp[nx][ny][nt], dp[x][y][t] + add)) {
					if (add == 0) {
						que.push_front({ nx,ny,nt });
					}
					else {
						que.push_back({ nx,ny,nt });
					}
				}
			}
		}
		{//C
			int nx = x + dxC[t];
			int ny = y + dyC[t];
			int nt = dzC[t];
			int add = s[x][y] == 'C' ? 0 : 1;
			if (nx == h - 1 && ny == w)chmin(ans, dp[x][y][t] + add);
			if (0 <= nx && nx < h && 0 <= ny && ny < w)
			{
				if (chmin(dp[nx][ny][nt], dp[x][y][t] + add)) {
					if (add == 0) {
						que.push_front({ nx,ny,nt });
					}
					else {
						que.push_back({ nx,ny,nt });
					}
				}
			}
		}
	}
	//int ans = INF;
	//rep(i, 4)chmin(ans, dp[h - 1][w - 1][i]);
	cout << ans << endl;
	//cout << endl;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t; cin >> t;
	while (t--)solve();
	return 0;
}

提出情報

ジャッジ結果