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>
typedef long long ll;
using namespace std;
char grid[4005][4005], cur;
bool vis[4005][4005];
int h, w, n, cnt, ans = 0;
bool valid(int i, int j){
return (i>=1 && i<=h && j>=1 && j<=w);
}
void dfs(int i, int j){
cnt++;
vis[i][j] = 1;
if(!vis[i+1][j] && valid(i+1,j) && grid[i+1][j]==cur){
grid[i+1][j] = (cur=='F' ? 'R' : 'F');
dfs(i+1,j);
}
if(!vis[i][j+1] && valid(i,j+1) && grid[i][j+1]==cur){
grid[i][j+1] = (cur=='F' ? 'R' : 'F');
dfs(i,j+1);
}
if(!vis[i-1][j] && valid(i-1,j) && grid[i-1][j]==cur){
grid[i-1][j] = (cur=='F' ? 'R' : 'F');
dfs(i-1,j);
}
if(!vis[i][j-1] && valid(i,j-1) && grid[i][j-1]==cur){
grid[i][j-1] = (cur=='F' ? 'R' : 'F');
dfs(i,j-1);
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>h>>w;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
cin>>grid[i][j];
if(grid[i][j] != '.') n++;
}
}
if(grid[1][1] == '.') {
cout<<"0\n";
return 0;
}
while(cnt<n){
cnt = 0;
cur = grid[1][1];
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++) vis[i][j] = 0;
}
grid[1][1] = (cur=='F' ? 'R' : 'F');
dfs(1,1);
++ans;
}
cout<<ans<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |