Submission #681712

#	Time	Username	Problem	Language	Result	Execution time	Memory
681712		MasterTaster	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1453 ms	979528 KiB

tracks

#include <iostream>
#include <string>
#include <vector>
#include <assert.h>

#define MAXN 4010
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second

using namespace std;

int n, m, a[MAXN][MAXN], cnt, ress;
int x[4], y[4];
bool vis[MAXN][MAXN];
vector<pii> nw, nww;

void dfs(int i, int j)
{
    //cout<<"usao "<<i<<" "<<j<<" "<<cnt<<endl;
    vis[i][j]=true;
    for (int k=0; k<4; k++)
    {
        ///(                out of bounds                )    (     visited     )    (         same            )
        if (/*i+x[k]<=0 || i+x[k]>n || j+y[k]<=0 || j+y[k]>m || */vis[i+x[k]][j+y[k]] || a[i+x[k]][j+y[k]]!=a[i][j]) continue;
        dfs(i+x[k], j+y[k]);
    }
}
void dfs2(int i, int j, int wh)
{
    vis[i][j]=true;
    for (int k=0; k<4; k++)
    {
        if (vis[i+x[k]][j+y[k]] || a[i+x[k]][j+y[k]]!=wh) continue;
        nww.pb({i+x[k], j+y[k]});
        dfs2(i+x[k], j+y[k], wh);
    }
}

int main() {
    cin>>n>>m;

    x[0]=-1; x[1]=0; x[2]=1; x[3]=0; ///up right down left
    y[0]=0; y[1]=1; y[2]=0; y[3]=-1; ///up right down left

    for (int i=0; i<=max(n, m); i++) vis[i][0]=vis[0][i]=vis[i][m+1]=vis[n+1][i]=true;
    for (int i=1; i<=n; i++)
    {
        string s; cin>>s;
        for (int j=1; j<=m; j++)
        {
            if (s[j-1]=='.') { a[i][j]=0; cnt++; }
            else if (s[j-1]=='R') a[i][j]=1;
            else a[i][j]=2;
        }
    }
    //for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) cout<<a[i][j]<<" "; cout<<endl; }

    dfs(1, 1);
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (vis[i][j]) { nw.pb({i, j}); cnt++; }
    ress=1;

    int which=3-a[1][1];
    //cout<<cnt<<endl;
    while (cnt<n*m)
    {
        nww.clear();

        for (auto p:nw)
        {
            dfs2(p.xx, p.yy, which);
            /*for (int i=0; i<4; i++)
            {
                if (!vis[p.xx+x[i]][p.yy+y[i]] && a[p.xx+x[i]][p.yy+y[i]]==which)
                {
                    vis[p.xx+x[i]][p.yy+y[i]]=true;
                    nww.pb({p.xx+x[i], p.yy+y[i]});
                }
            }*/
        }
        if (nww.size()==0) assert(0);


        nw.clear();
        for (int i=0; i<nww.size(); i++) { nw.pb(nww[i]); cnt++; }

        ress++;
        which=3-which;
    }
    cout<<ress;
}
/*
4 4
RRRR
.F.R
.FFR
.R.R
 */

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:88:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for (int i=0; i<nww.size(); i++) { nw.pb(nww[i]); cnt++; }
      |                       ~^~~~~~~~~~~

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