제출 #988917

#제출 시각아이디문제언어결과실행 시간메모리
988917IvanYamasakiTracks in the Snow (BOI13_tracks)C++17
51.88 / 100
2087 ms829416 KiB
#include <bits/stdc++.h>
using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define pii pair<int , int>
#define vi vector<int>
#define pb push_back
#define f first
#define s second
#define ll long long
#define grid vector<vector<int>>

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 1e5+10;

int h,w; 
grid g;
int isR=0, isF=0, ans=1; 

pii moves[] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

bool valid(pii coord, int a){
    int x=coord.f, y=coord.s;
    return x>=0 and x<h and y>=0 and y<w and g[x][y]==a;
}

void dfs(pii src, int a){

    for(pii i : moves){
        int x = src.f+i.f, y=src.s+i.s; 
        if(valid({x,y}, a)) {
            if(g[x][y]==1) {
                if(isR!=0) g[x][y]=2; else g[x][y]=0;
                isF--; isR++;
            }
            else if(g[x][y]==2){
                if(isF!=0) g[x][y]=1; else g[x][y]=0;
                isR--; isF++;
            } 
            dfs({x,y}, a);
        }
    } 
}

int main(){ _

    cin>>h>>w; g.resize(h, vi(w));
    for(int i=0; i<h; i++) for(int j=0; j<w; j++){
        char c; cin >>c;
        if(c=='.') g[i][j]=0;
        else if(c=='F'){ g[i][j]=1; isF++; }
        else if(c=='R'){ g[i][j]=2; isR++; }
    }
    while(isR!=0 and isF!=0){
        ans++; dfs({h-1,w-1}, g[h-1][w-1]);
    }

    cout << ans << endl;

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