#include <bits/stdc++.h>
using namespace std;
int n, m;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
bool check(int nx, int ny){
return (nx >= 0 && nx < n && ny >= 0 && ny < m);
}
struct item{
int x, y, dist;
};
struct comp{
bool operator()(item a, item b){
return (a.dist < b.dist) || (a.dist == b.dist && make_pair(a.x, a.y) < make_pair(b.x, b.y));
}
};
int bfs(vector<vector<char>>& grid){
priority_queue<item, vector<item>, comp> q;
q.push({0, 0, 1});
vector<vector<int>> dist(n, vector<int>(m, 1e9));
dist[0][0] = 1;
while (!q.empty()){
item i = q.top(); q.pop();
if (dist[i.x][i.y] != i.dist) continue;
for (int j = 0; j < 4; j++){
int nx = i.x + dx[j], ny = i.y + dy[j];
if (!check(nx, ny)) continue;
if (grid[nx][ny] == '.') continue;
int ndist = i.dist + (grid[nx][ny] != grid[i.x][i.y]);
if (ndist < dist[nx][ny]){
dist[nx][ny] = ndist;
q.push({nx, ny, ndist});
}
}
}
//max distance
int mx = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
//cout << (dist[i][j] == 1e9 ? 0 : dist[i][j]) << ' ';
if (grid[i][j] == '.') continue;
if (dist[i][j] > mx){
mx = dist[i][j];
}
}
//cout << '\n';
}
return mx;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
vector<vector<char>> grid(n, vector<char>(m));
vector<int> cnt(2, 0); //r, f
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> grid[i][j];
if (grid[i][j] == 'F') cnt[1]++;
if (grid[i][j] == 'R') cnt[0]++;
}
}
//empty
if (grid[0][0] == '.'){
cout << "0\n";
return 0;
}
//ans
cout << bfs(grid) << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2093 ms |
3536 KB |
Time limit exceeded |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Execution timed out |
2091 ms |
2952 KB |
Time limit exceeded |
| 5 |
Correct |
1653 ms |
1032 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
348 KB |
Output is correct |
| 8 |
Correct |
127 ms |
348 KB |
Output is correct |
| 9 |
Correct |
4 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1449 ms |
912 KB |
Output is correct |
| 11 |
Execution timed out |
2035 ms |
1048 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2067 ms |
1372 KB |
Time limit exceeded |
| 13 |
Correct |
1644 ms |
1024 KB |
Output is correct |
| 14 |
Correct |
1637 ms |
1032 KB |
Output is correct |
| 15 |
Execution timed out |
2035 ms |
2040 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2061 ms |
3532 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2067 ms |
2360 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2013 ms |
3028 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
856 KB |
Output is correct |
| 2 |
Execution timed out |
2079 ms |
10452 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2095 ms |
95580 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2060 ms |
22612 KB |
Time limit exceeded |
| 5 |
Correct |
211 ms |
53584 KB |
Output is correct |
| 6 |
Execution timed out |
2072 ms |
194172 KB |
Time limit exceeded |
| 7 |
Correct |
2 ms |
856 KB |
Output is correct |
| 8 |
Correct |
2 ms |
856 KB |
Output is correct |
| 9 |
Execution timed out |
2041 ms |
860 KB |
Time limit exceeded |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Correct |
3 ms |
860 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Execution timed out |
2091 ms |
10536 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2045 ms |
6188 KB |
Time limit exceeded |
| 15 |
Correct |
24 ms |
6236 KB |
Output is correct |
| 16 |
Execution timed out |
2031 ms |
4804 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2012 ms |
25084 KB |
Time limit exceeded |
| 18 |
Correct |
108 ms |
24088 KB |
Output is correct |
| 19 |
Execution timed out |
2028 ms |
22868 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2024 ms |
21608 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2096 ms |
56308 KB |
Time limit exceeded |
| 22 |
Correct |
212 ms |
53468 KB |
Output is correct |
| 23 |
Execution timed out |
2085 ms |
46512 KB |
Time limit exceeded |
| 24 |
Correct |
196 ms |
54032 KB |
Output is correct |
| 25 |
Correct |
561 ms |
94704 KB |
Output is correct |
| 26 |
Correct |
1487 ms |
72976 KB |
Output is correct |
| 27 |
Execution timed out |
2013 ms |
194420 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2066 ms |
193452 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2008 ms |
195168 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2054 ms |
93504 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2041 ms |
111496 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2040 ms |
145300 KB |
Time limit exceeded |
