Submission #1176348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176348		julia_08	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	1222 ms	1080872 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 4e3 + 10;

char a[MAXN][MAXN];

int marc[MAXN][MAXN];

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

int n, m;

bool check(int i, int j){
  return i > 0 && j > 0 && i <= n && j <= m && !marc[i][j];
}

void dfs(int i, int j){

  marc[i][j] = 1;

  for(int k=0; k<4; k++){
    int ni = i + dx[k], nj = j + dy[k];
    if(check(ni, nj)) dfs(ni, nj);
  }

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;

  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      cin >> a[i][j];
    }
  }

  int ans = 0;

  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      if(!marc[i][j]){
        if(a[i][j] == 'R') dfs(i, j), ans ++;
      }
    }
  }

  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      if(a[i][j] == 'F') marc[i][j] = 0;
    }
  }

  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      if(!marc[i][j]){
        if(a[i][j] == 'F') dfs(i, j), ans ++;
      }
    }
  }

  cout << ans << "\n";

  return 0;
}

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