This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int>PI;
typedef pair<ll, ll > PL;
typedef vector<int>VI;
typedef vector<ll>VL;
#define FF first
#define SS second
const int mod = 1e9 + 7;
const int INF = 1e9;
const int N = 4000 + 5;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int dist[N][N];
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
char grid[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> grid[i][j];
int ans = 0, f1 = 0;
deque<pair<int, int>>qu;
qu.push_front({0, 0});
dist[0][0] = 1;
while (!qu.empty())
{
auto node = qu.front();
qu.pop_front();
ans = max(ans, dist[node.FF][node.SS]);
for (int d = 0; d < 4; d++)
{
int nx = node.FF + dx[d], ny = node.SS + dy[d];
if (nx<0 or ny<0 or nx >= n or ny >= m or grid[nx][ny] == '.' or dist[nx][ny])continue;
int ndist = dist[node.FF][node.SS] + (grid[node.FF][node.SS] != grid[nx][ny]);
dist[nx][ny] = ndist;
if (dist[nx][ny] == dist[node.FF][node.SS])
qu.push_front({nx, ny});
else qu.push_back({nx, ny});
}
}
cout << ans << endl;
cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}
Compilation message (stderr)
tracks.cpp: In function 'int main()':
tracks.cpp:27:15: warning: unused variable 'f1' [-Wunused-variable]
27 | int ans = 0, f1 = 0;
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |