Submission #553766

#	Time	Username	Problem	Language	Result	Execution time	Memory
553766		Uzouf	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	2083 ms	10264 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
//#define endl "\n"
const int mod = (int) 1e9 + 7;
const int N=1005;

int n,m,ans,nm;
char c,tmp;
char v[N][N];
char imp[N][N];
bool vis[N][N];
bool bl;

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

bool chk(int i,int j) {
  return i>=0 && j>=0 && i<n && j<m && !vis[i][j] && v[i][j]==tmp && imp[i][j]!='*';
}

void bfs(int a,int b) {
  queue<pair<int,int> > q; q.push({a,b});
  while (!q.empty()) {
    int i=q.front().first;
    int j=q.front().second;
    q.pop();
    vis[i][j]=true;

    for (int p=0;p<4;p++) {
      int ii=i+dx[p],jj=j+dy[p];
      if (chk(ii,jj)) {
      nm--; bl=true; bfs(ii,jj);}
    }
  }

}


signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(".in", "r", stdin); freopen(".out", "w", stdout);

    cin>>n>>m;
    for (int i=0;i<n;i++) {
      for (int j=0;j<m;j++) {
        cin>>v[i][j];
        if (v[i][j]=='.') {imp[i][j]='*';}
        else {nm++;}
      }
    }

    c=v[0][0]; tmp=v[0][0]; nm--; bfs(0,0); ans++;

    while (nm>0) {
      bl=false;
      for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {

          if (vis[i][j] && v[i][j]==c && imp[i][j]!='*') {
            if (c=='R') {tmp='F';}
            else {tmp='R';}
            nm--; bfs(i,j);
            imp[i][j]='*';
          }

        }
      }
      c=tmp;
      if (bl) {ans++;}
    }
    cout<<ans;
}

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