Submission #719436

#	Time	Username	Problem	Language	Result	Execution time	Memory
719436		YENGOYAN	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	1460 ms	80896 KiB

tracks

/*
                                    //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
                                    \\                                    //
                                    //  271828___182845__904523__53602__  \\
                                    \\  87___47____13______52____66__24_  //
                                    //  97___75____72______47____09___36  \\
                                    \\  999595_____74______96____69___67  //
                                    //  62___77____24______07____66__30_  \\
                                    \\  35___35____47______59____45713__  //
                                    //                                    \\
                                    \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>
#include <functional>

using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e18;

vector<int> dx = { 1, 0, -1, 0, 1, -1, 1, -1 };
vector<int> dy = { 0, -1, 0, 1, -1, 1, 1, -1 };

void solve() {
  int n, m; cin >> n >> m;
  vector<string> v(n);
  for(int i = 0; i < n; ++i){
    cin >> v[i];
  }
  vector<vector<int>> vis(n, vector<int> (m));
  int c = 0;
  for(int i =0 ; i < n; ++i){
    for(int j =0 ; j < m; ++j){
      if(vis[i][j] || v[i][j] == '.') {
        continue;
      }
      ++c;
      queue<pair<int, int>> q;
      q.push({i, j});
      vis[i][j] = 1;
      while(q.size()){
        int ii = q.front().first, jj = q.front().second;
        q.pop();
        for(int k = 0; k < 4; ++k){
          int to_i = ii + dx[k], to_j = jj + dy[k];
          if(to_i < 0 || to_j < 0 || to_i == n || to_j == m){
            continue;
          }
          if(v[to_i][to_j] == '.'){
            if(v[i][j] == 'R' && (vis[to_i][to_j] & 1) == 0){
              vis[to_i][to_j] |= 1;
              q.push({to_i, to_j});
            }
            else if(v[i][j] == 'F' && (vis[to_i][to_j] & 2) == 0){
              vis[to_i][to_j] |= 2;
              q.push({to_i, to_j});
            }
          }
          else if(v[to_i][to_j] == v[i][j] && !vis[to_i][to_j]){
            vis[to_i][to_j] = 1;
            q.push({to_i, to_j});
          }
        }
      }
    }
  }
  if(!c) cout << "0\n";
  else cout << c / 2 + 1 << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 // int t; cin >> t; while (t--)
    solve();

}

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