This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
struct P{
ll x, y;
};
void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
const int N = 4001;
char grid[N][N];
int dist[N][N];
int h, w;
int valid(int x, int y){
return (0 <= x && x < h) && (0 <= y && y < w);
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
signed main(){
fastio;
cin >> h >> w;
for (int i=0; i<h; i++){
for (int j=0; j<w; j++){
cin >> grid[i][j];
}
}
memset(dist, -1, sizeof(dist));
int ans=1;
queue<pair<int, int>> q0, q1;
dist[0][0] = 1;
q0.push({0, 0});
int x, y;
int ctr=0;
while (!q0.empty() || !q1.empty()){
while (!q0.empty()){
tie(x, y) = q0.front(); q0.pop();
ans = max(ans, dist[x][y]);
for (int i=0; i<4; i++){
int a, b;
a = dx[i]+x;
b = dy[i]+y;
if (!valid(a, b) || grid[a][b] == '.' || dist[a][b] != -1) continue;
dist[a][b] = dist[x][y];
if (grid[a][b] != grid[x][y]){
dist[a][b]++;
q1.push({a, b});
}
else q0.push({a, b});
}
}
swap(q0, q1);
}
cout << ans << '\n';
}
Compilation message (stderr)
tracks.cpp: In function 'int main()':
tracks.cpp:46:9: warning: unused variable 'ctr' [-Wunused-variable]
46 | int ctr=0;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |