| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 681090 | MasterTaster | Tracks in the Snow (BOI13_tracks) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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> nw1, nw2;
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]);
}
}
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]) { nw2.pb({i, j}); cnt++; }
ress=1;
nw1.clear();
int which=3-a[1][1];
//cout<<cnt<<endl;
while (cnt<n*m)
{
vector<pii> nww;
nww.clear();
for (auto p:nw1)
{
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]});
}
}
}
for (auto p:nw2)
{
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);
nw1=nw2;
nw2.clear();
for (int i=0; i<nww.size(); i++) { nw2.pb(nww[i]); cnt++; }
ress++;
which=3-which;
}
cout<<ress;
}