Submission #72575776

---

Source Code Expand

#include <bits/extc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define repp(i, m, n) for(int i = (int)(m); i < (int)n; i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define fore(x, a) for (auto &x : a)
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
#define co(a, x, b) (a <= x && x < b)
#define INF ((1LL<<62)-(1LL<<31))

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main() {
	int h, w;
	cin >> h >> w;
	vector<string> s(h);
	rep(i, h) cin >> s[i];
	
	vector<vi> g(h*w);
	rep(i, h) {
		rep(j, w-1) {
			int k = i*w+j;
			if (s[i][j] != s[i][j+1]) {
				g[k].push_back(k+1);
				g[k+1].push_back(k);
			}
		}
	}
	rep(j, w) {
		rep(i, h-1) {
			int k = i*w+j;
			if (s[i][j] != s[i+1][j]) {
				g[k].push_back(k+w);
				g[k+w].push_back(k);
			}
		}
	}

	vi dist(h*w, -1);
	queue<int> que;
	dist[0] = 0;
	que.push(0);
	while (!que.empty()) {
		int v = que.front();
		que.pop();
		for (int nv : g[v]) {
			if (dist[nv] != -1) continue;
			dist[nv] = dist[v] + 1;
			que.push(nv);
		}
	}

	// rep(i, h) {
	// 	rep(j, w) {
	// 		cout << dist[i*w+j];
	// 	}
	// 	cout << endl;
	// }
	cout << dist[h*w-1] << endl;
}

Submission Info

Judge Result