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 int long long
int h,w;
int hsh(int i, int j){
// 0 <= i < h
// 0 <= j < w
return (i*w)+j;
}
pair<int,int> unhsh(int x){
return {x/w,x%w};
}
signed main() {
cin >> h >> w;
int grid[h][w];
bool visited[h][w];
for (int i = 0; i<h; i++){
for (int j = 0; j<w; j++){
char a;
cin >> a;
if (a == '.') grid[i][j] = 0;
if (a == 'R') grid[i][j] = 1;
if (a == 'F') grid[i][j] = 2;
visited[i][j] = false;
}
}
vector<int> dx = {0,1,0,-1};
vector<int> dy = {1,0,-1,0};
int mxn = hsh(h-1,w-1);
vector<int> dist(mxn+1, 1e9);
deque<pair<int,int>> q;
q.push_front({0,0});
dist[0] = 1;
int ans = 0;
while (!q.empty()){
pair<int,int> v = q.front();
int vhsh = hsh(v.first,v.second);
q.pop_front();
ans = max(ans,dist[vhsh]);
if (visited[v.first][v.second]) continue;
visited[v.first][v.second] = true;
int r = v.first;
int c = v.second;
for (int k = 0; k<4; k++){
int rr = r + dx[k];
int cc = c + dy[k];
if (rr < 0 || rr >= h || cc < 0 || cc >= w) continue;
if (visited[rr][cc]) continue;
if (grid[rr][cc] == 0) continue;
int khsh = hsh(rr,cc);
if (dist[vhsh] + (grid[r][c] != grid[rr][cc]) < dist[khsh]){
dist[khsh] = dist[vhsh] + (grid[r][c] != grid[rr][cc]);
if (grid[rr][cc] != grid[r][c]){
q.push_back({rr,cc});
}
else{
q.push_front({rr,cc});
}
}
}
}
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |