Submission #1306355

#TimeUsernameProblemLanguageResultExecution timeMemory
1306355khanhphucscratchTracks in the Snow (BOI13_tracks)C++20
100 / 100
636 ms88792 KiB
#include<bits/stdc++.h>
using namespace std;
queue<pair<int, int>> w[2];
vector<pair<int, int>> option = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int a[4005][4005];
bool visited[4005][4005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m; cin>>n>>m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char x; cin>>x;
            if(x == '.') a[i][j] = 2;
            else if(x == 'F') a[i][j] = 1;
            else a[i][j] = 0;
        }
    }
    int ans = 0, target = a[1][1];
    w[target].push({1, 1});
    while(true){
        if(w[target].size() == 0) target ^= 1;
        if(w[target].size() == 0) break;
        while(w[target].size() > 0){
            int r = w[target].front().first, c = w[target].front().second;
            //cerr<<"A"<<r<<" "<<c<<" "<<a[r][c]<<endl;
            visited[r][c] = 1;
            w[target].pop();
            for(pair<int, int> i : option){
                int nr = r+i.first, nc = c+i.second;
                if(nr < 1 || nr > n || nc < 1 || nc > m) continue;
                if(visited[nr][nc] == 0 && a[nr][nc] <= 1){
                    visited[nr][nc] = 1;
                    w[a[nr][nc]].push({nr, nc});
                }
            }
        }
        ans++;
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...