Submission #877556

#	Time	Username	Problem	Language	Result	Execution time	Memory
877556		asli_bg	Tracks in the Snow (BOI13_tracks)	C++11	47.50 / 100	2099 ms	141396 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define MOD 1000000007

const int MAXN=4e3+1;

int vis[MAXN][MAXN];

int grid[MAXN][MAXN];

int h,w;

int xyon[5]={1,0,-1,0};
int yyon[5]={0,-1,0,1};

int say=0;

bool isvalid(int x,int y,int deg){
    if(x>=h or x<0 or y>=w or y<0) return false;
    if(grid[x][y]==-1) return false;
    if(grid[x][y]!=deg) return false;
    return true;
}

void bfs(int x,int y){
    queue<pii> q;
    q.push({x,y});
    vis[x][y]=true;
    say++;

    int deg=grid[x][y];

    grid[x][y]=!deg;

    while(!q.empty()){
        auto el=q.front();
        q.pop();

        for(int i=0;i<4;i++){
            int newx=el.fi+xyon[i];
            int newy=el.se+yyon[i];

            if(isvalid(newx,newy,deg) and !vis[newx][newy]){
                //cout<<grid[el.fi][el.se]<<"-->"<<grid[newx][newy]<<endl;
                vis[newx][newy]=true;
                q.push({newx,newy});
                grid[newx][newy]=!deg;
                say++;

            }

        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
 
    //ifstream cin("lepus.in");
    //ofstream cout("lepus.out");

    cin>>h>>w;

    map<char,int> anim;
    anim['F']=1;
    anim['R']=0;
    anim['.']=-1;

    int all_steps=0;

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            char c;
            cin>>c;
            grid[i][j]=anim[c];
            if(grid[i][j]!=-1){
                all_steps++;
            }
        }
    }

    //cout<<all_steps<<endl;

    

    int cev=0;

    while(all_steps!=say){
        say=0;
        bfs(0,0);
        //cout<<"s: "<<say<<endl;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                vis[i][j]=false;
            }
        }
        cev++;
    }

    cout<<cev<<endl;

    /*for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout<<grid[i][j]<<' ';
        }
        cout<<endl;
    }*/

}
    

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