#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define space <<' '<<
#define endl '\n'
#define inf 1e14
#define F first
#define S second
#define PB push_back
#define PF push_front
#define md(a) ((a+mod)%mod)
#define MP(a,b) make_pair(a,b)
#define MT(a,b,c) make_tuple(a,b,c)
typedef long long ll;
using namespace std;
template<typename t> using heap=
priority_queue<t,vector<t>,greater<t>>;
const int mx = 4005;
int h,w;
bool seen[mx][mx];
char state[mx][mx];
deque<pair<int,int>> l[2];
void c(int i,int j,char s,bool p){
if(i<0||h<=i||j<0||w<=j)return;
if (state[i][j]=='.') return;
if(seen[i][j]) return;
if(state[i][j]==s)
l[p].push_front(MP(i,j));
else
l[!p].push_front(MP(i,j));
}
int main(){
std::ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>h>>w;
for(int i=0;i<h;i++)
for(int j=0;j<w;j++)
cin>>state[i][j];
int pc=0,cnt=0;
char cc=state[h-1][w-1];
l[pc].PB(MP(h-1,w-1));
if(cc=='.'){
cout<<0;
return 0;
}
while(!l[pc].empty()){
auto d=l[pc].back();
seen[d.F][d.S]=1;
l[pc].pop_back();
c(d.F+1,d.S,cc,pc);
c(d.F-1,d.S,cc,pc);
c(d.F,d.S+1,cc,pc);
c(d.F,d.S-1,cc,pc);
if(l[pc].empty()){
pc=!pc;cnt++;
cc=((cc=='F')?'R':'F');
}
}
cout<<cnt;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1838 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1585 ms |
76612 KB |
Output is correct |
| 4 |
Execution timed out |
2078 ms |
768672 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2063 ms |
463880 KB |
Time limit exceeded |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1513 ms |
76816 KB |
Output is correct |
| 8 |
Execution timed out |
2056 ms |
757756 KB |
Time limit exceeded |
| 9 |
Correct |
6 ms |
4700 KB |
Output is correct |
| 10 |
Execution timed out |
2133 ms |
999752 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2086 ms |
815868 KB |
Time limit exceeded |
| 12 |
Runtime error |
1980 ms |
1048576 KB |
Execution killed with signal 9 |
| 13 |
Execution timed out |
2078 ms |
428580 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2031 ms |
429356 KB |
Time limit exceeded |
| 15 |
Runtime error |
1940 ms |
1048576 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
1909 ms |
1048576 KB |
Execution killed with signal 9 |
| 17 |
Execution timed out |
2111 ms |
859200 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2062 ms |
768852 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
30300 KB |
Output is correct |
| 2 |
Execution timed out |
2117 ms |
829240 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2064 ms |
356828 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2068 ms |
267404 KB |
Time limit exceeded |
| 5 |
Correct |
149 ms |
32596 KB |
Output is correct |
| 6 |
Execution timed out |
2051 ms |
1048576 KB |
Time limit exceeded |
| 7 |
Correct |
12 ms |
31836 KB |
Output is correct |
| 8 |
Correct |
11 ms |
30300 KB |
Output is correct |
| 9 |
Execution timed out |
2100 ms |
226144 KB |
Time limit exceeded |
| 10 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
15 ms |
31068 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 13 |
Execution timed out |
2129 ms |
842888 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2058 ms |
406728 KB |
Time limit exceeded |
| 15 |
Correct |
17 ms |
10584 KB |
Output is correct |
| 16 |
Execution timed out |
2070 ms |
555944 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2061 ms |
404368 KB |
Time limit exceeded |
| 18 |
Correct |
65 ms |
20560 KB |
Output is correct |
| 19 |
Execution timed out |
2045 ms |
268444 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2070 ms |
234772 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2084 ms |
260812 KB |
Time limit exceeded |
| 22 |
Correct |
163 ms |
32752 KB |
Output is correct |
| 23 |
Execution timed out |
2091 ms |
331272 KB |
Time limit exceeded |
| 24 |
Correct |
138 ms |
33620 KB |
Output is correct |
| 25 |
Correct |
309 ms |
47444 KB |
Output is correct |
| 26 |
Execution timed out |
2086 ms |
738688 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2072 ms |
743784 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2072 ms |
1048576 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2048 ms |
715400 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2064 ms |
770396 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2025 ms |
1048576 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2064 ms |
641512 KB |
Time limit exceeded |
