/*
This code belongs to Aadit Ambadkar
Date: 2022-03-07 21:34:47
Problem: tis
*/
#include <bits/stdc++.h>
using namespace::std;
typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define MOD 1000000007
#define FF first
#define SS second
int n, m;
int board[4005][4005];
bool vis[4005][4005];
int main() {
fastio;
cin >> n >> m;
F0R(i, n) {
string s;
cin >> s;
F0R(j, m) {
if (s[j]=='F') board[i][j]=1;
else if (s[j]=='R') board[i][j]=2;
else board[i][j]=0;
vis[i][j]=false;
}
}
// F0R(i, n) {
// F0R(j, m) {
// cout << board[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
pq.push({1, {0, 0}});
int ans = 0;
while (!pq.empty()) {
auto p = pq.top(); pq.pop();
int g = p.FF, u = p.SS.FF, v = p.SS.SS;
if (vis[u][v]) continue;
// cout << u << " " << v << " " << g << "\n";
ans = max(ans, g);
vis[u][v]=true;
if (u < n-1 && !vis[u+1][v] && board[u+1][v]!=0) pq.push({g+((board[u][v]==board[u+1][v]) ? 0 : 1), {u+1, v}});
if (u > 0 && !vis[u-1][v] && board[u-1][v]!=0) pq.push({g+((board[u][v]==board[u-1][v]) ? 0 : 1), {u-1, v}});
if (v < m-1 && !vis[u][v+1] && board[u][v+1]!=0) pq.push({g+((board[u][v]==board[u][v+1]) ? 0 : 1), {u, v+1}});
if (v > 0 && !vis[u][v-1] && board[u][v-1]!=0) pq.push({g+((board[u][v]==board[u][v-1]) ? 0 : 1), {u, v-1}});
// cout << "\n";
}
cout << ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
100 ms |
5636 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
704 KB |
Output is correct |
4 |
Correct |
54 ms |
5384 KB |
Output is correct |
5 |
Correct |
7 ms |
3020 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
716 KB |
Output is correct |
8 |
Correct |
3 ms |
844 KB |
Output is correct |
9 |
Correct |
1 ms |
1096 KB |
Output is correct |
10 |
Correct |
7 ms |
2636 KB |
Output is correct |
11 |
Correct |
13 ms |
2248 KB |
Output is correct |
12 |
Correct |
31 ms |
3148 KB |
Output is correct |
13 |
Correct |
6 ms |
3020 KB |
Output is correct |
14 |
Correct |
6 ms |
3016 KB |
Output is correct |
15 |
Correct |
60 ms |
5672 KB |
Output is correct |
16 |
Correct |
98 ms |
5644 KB |
Output is correct |
17 |
Correct |
35 ms |
5312 KB |
Output is correct |
18 |
Correct |
54 ms |
5520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
30796 KB |
Output is correct |
2 |
Correct |
175 ms |
17976 KB |
Output is correct |
3 |
Correct |
471 ms |
94456 KB |
Output is correct |
4 |
Correct |
130 ms |
33736 KB |
Output is correct |
5 |
Correct |
144 ms |
67912 KB |
Output is correct |
6 |
Execution timed out |
2095 ms |
119184 KB |
Time limit exceeded |
7 |
Correct |
14 ms |
32204 KB |
Output is correct |
8 |
Correct |
18 ms |
30896 KB |
Output is correct |
9 |
Correct |
8 ms |
720 KB |
Output is correct |
10 |
Correct |
1 ms |
456 KB |
Output is correct |
11 |
Correct |
16 ms |
31676 KB |
Output is correct |
12 |
Correct |
2 ms |
1612 KB |
Output is correct |
13 |
Correct |
174 ms |
17992 KB |
Output is correct |
14 |
Correct |
95 ms |
11972 KB |
Output is correct |
15 |
Correct |
22 ms |
13124 KB |
Output is correct |
16 |
Correct |
95 ms |
6704 KB |
Output is correct |
17 |
Correct |
485 ms |
36420 KB |
Output is correct |
18 |
Correct |
78 ms |
35652 KB |
Output is correct |
19 |
Correct |
130 ms |
33652 KB |
Output is correct |
20 |
Correct |
131 ms |
31064 KB |
Output is correct |
21 |
Correct |
292 ms |
70208 KB |
Output is correct |
22 |
Correct |
151 ms |
67920 KB |
Output is correct |
23 |
Correct |
855 ms |
57192 KB |
Output is correct |
24 |
Correct |
133 ms |
69436 KB |
Output is correct |
25 |
Correct |
404 ms |
94452 KB |
Output is correct |
26 |
Execution timed out |
2033 ms |
80852 KB |
Time limit exceeded |
27 |
Execution timed out |
2031 ms |
92828 KB |
Time limit exceeded |
28 |
Execution timed out |
2049 ms |
114252 KB |
Time limit exceeded |
29 |
Execution timed out |
2104 ms |
115364 KB |
Time limit exceeded |
30 |
Execution timed out |
2066 ms |
113696 KB |
Time limit exceeded |
31 |
Execution timed out |
2108 ms |
74696 KB |
Time limit exceeded |
32 |
Execution timed out |
2093 ms |
93604 KB |
Time limit exceeded |