이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// In the name of God
// : )
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 4000 + 5;
int di[4] = {1, -1, 0, 0}, dj[4] = {0, 0, 1, -1};
int H, W;
string grid[N];
int dis[N][N];
bool valid(int i, int j) {
return i >= 0 && j >= 0 && i < H && j < W && grid[i][j] != '.';
}
void solve() {
cin >> H >> W;
for (int i = 0; i < H; i++)
cin >> grid[i];
memset(dis, 63, sizeof dis);
dis[0][0] = 0;
deque<pair<int, int> > dq;
dq.pb(mp(0, 0));
int ans = 0;
while (!dq.empty()) {
int i = dq.front().fi, j = dq.front().se;
dq.pop_front();
ans = dis[i][j] + 1;
for (int t = 0; t < 4; t++) {
int x = i + di[t], y = j + dj[t];
if (valid(x, y) && dis[x][y] > 1e9) {
if (grid[x][y] == grid[i][j]) {
dq.push_front(mp(x, y));
dis[x][y] = dis[i][j];
}
else {
dq.pb(mp(x, y));
dis[x][y] = dis[i][j] + 1;
}
}
}
}
cout << ans << '\n';
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |