제출 #811130

#제출 시각아이디문제언어결과실행 시간메모리
811130davinpwkTracks in the Snow (BOI13_tracks)C++14
2.19 / 100
2097 ms16276 KiB
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

char grid[4005][4005], cur;
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++;
    if(valid(i+1,j) && grid[i+1][j]==cur){
        grid[i+1][j] = (cur=='F' ? 'R' : 'F');
        dfs(i+1,j);
    }
    if(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];
        grid[1][1] = (cur=='F' ? 'R' : 'F');
        dfs(1,1);
        ++ans;
        // for(int i=1;i<=h;i++){
        //     for(int j=1;j<=w;j++) cout<<grid[i][j]<<' ';
        //     cout<<'\n';
        // }
    }

    cout<<ans<<'\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...