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;
typedef pair<int, int> pii;
#define f first
#define s second
int N, M;
char arr[4100][4100];
int depth[4100][4100];
struct comp{
bool operator()(const pair<pii, int> &a, const pair<pii, int> &b){
return a.s > b.s;
}
};
int xd[4] = {1, -1, 0, 0};
int yd[4] = {0, 0, 1, -1};
int main(){
cin >> N >> M;
for (int i = 1; i <= N; i++){
for (int j = 1; j <= M; j++){
cin >> arr[i][j];
}
}
priority_queue<pair<pii, int>, vector<pair<pii, int> >, comp> pq;
pq.push({{1, 1}, 1});
depth[1][1] = 1;
while (!pq.empty()){
int x = pq.top().f.f;
int y = pq.top().f.s;
int w = pq.top().s;
pq.pop();
//if (depth[x][y] >= w) continue;
for (int i = 0; i < 4; i++){
int nx = x+xd[i];
int ny = y+yd[i];
if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && arr[nx][ny] != '.' && !depth[nx][ny]){
if (arr[x][y] == arr[nx][ny])
depth[nx][ny] = depth[x][y];
else
depth[nx][ny] = depth[x][y]+1;
pq.push({{nx, ny}, depth[nx][ny]});
}
}
}
int ans = 0;
for (int i = 1; i <= N; i++){
for (int j = 1; j <= M; j++){
ans = max(ans, depth[i][j]);
}
}
cout << ans << "\n";
}
Compilation message (stderr)
tracks.cpp: In function 'int main()':
tracks.cpp:36:7: warning: unused variable 'w' [-Wunused-variable]
36 | int w = pq.top().s;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |