Submission #812244

#	Time	Username	Problem	Language	Result	Execution time	Memory
812244		makanhulia	Tracks in the Snow (BOI13_tracks)	C++17	30 / 100	2079 ms	9048 KiB

tracks

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define REP(i,a,b)for(int i=a;i<b;i++)
#define fi first
#define se second
using namespace std;
using pii=pair<int, int>;

int color[1000][1000];
bool visited[1000][1000];
int on=0;
int col=-1;
int h, w;

void bfs() {
    queue<pii> q;
    q.push({0,0});
    while(q.size()){
        auto top=q.front();
        q.pop();
        if(top.fi<0)continue;
        if(top.fi>=h)continue;
        if(top.se<0)continue;
        if(top.se>=w)continue;
        if(visited[top.fi][top.se])continue;
        visited[top.fi][top.se]=true;
        if((color[top.fi][top.se]!=col) && (color[top.fi][top.se]!=(-1))){
            continue;
        }
        if(color[top.fi][top.se]!=(-1))on--;
        color[top.fi][top.se]=-1;
        q.push({top.fi+1, top.se});
        q.push({top.fi-1, top.se});
        q.push({top.fi, top.se+1});
        q.push({top.fi, top.se-1});
    }
}

#undef int
int main() {
#define int long long
    cin>>h>>w;
    assert(max(h, w)<1000);
    REP(i,0,h){
        REP(j,0,w){
            char c;cin>>c;
            if(c=='.')color[i][j]=0;
            if(c=='R')color[i][j]=1;
            if(c=='F')color[i][j]=2;
            if(color[i][j])on++;
        }
    }
    col=color[0][0];
    int ans=0;
    // on=1;
    while(true){
        ans++;
        bfs();
        memset(visited,0,sizeof visited);
        bool clear=true;
        REP(i,0,h){
            REP(j,0,w){
                if(color[i][j]>=1)clear=false;
                // cout<<color[i][j]<<" ";
                // if(color[i][j]!=-1)cout<<" ";
            }
            // cout<<endl;
        }
        if(clear)break;
        col = 3-col;
    }
    cout<<ans<<endl;
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 70