Submission #719618

#	Time	Username	Problem	Language	Result	Execution time	Memory
719618		YENGOYAN	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1253 ms	101128 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 ans = 0;
  queue<pair<int, int>> q;
  q.push({0, 0});
  vis[0][0] = 1;
  while(q.size()){
    queue<pair<int, int>> new_q;
    ++ans;
    int st_i = q.front().first, st_j = q.front().second;
    while(q.size()){
      int i = q.front().first, j = q.front().second;
      q.pop();
      for(int k = 0; k < 4; ++k){
        int to_i = i + dx[k], to_j = j + dy[k];
        if(to_i < 0 || to_j < 0 || to_i == n || to_j == m) {
          continue;
        }
        if(vis[to_i][to_j]){
          continue;
        }
        if(v[to_i][to_j] == v[st_i][st_j]){
          q.push({to_i, to_j});
          vis[to_i][to_j] = 1;
        }
        else if(v[to_i][to_j] != '.'){
          new_q.push({to_i, to_j});
          vis[to_i][to_j] = 1;
        }
      }
    }
    q = new_q;
  }
  cout << ans << "\n";
}

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

}

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