Submission #561974

#	Time	Username	Problem	Language	Result	Execution time	Memory
561974		HashirGJ8842	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1390 ms	76256 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
 
int iterate(int i, int j, char temp, 
    vector<vector<bool>> &visited,
    vector<vector<char>> &arr) {
  if(i < 0 || j < 0 || i >= (int)visited.size() || j >= (int)visited[0].size()) 
    return -1;
  if(visited[i][j]) return -1;
  visited[i][j] = true;
  if(arr[i][j] == '.') return -1;
  return arr[i][j] == temp;
}

void solve() {
  int r, c;
  cin >> r >> c;
  vector<vector<char>> arr(r, vector<char>(c));
  for(auto &x: arr) {
    for(auto &y: x) cin >> y;
  }

  deque<pair<int, int>> d;
  d.push_back({0, 0});
  int answer = 1;
  char temp = arr[0][0];
  char prev = arr[0][0];
  vector<vector<bool>> visited(r, vector<bool>(c, false));
  visited[0][0] = true;
  while(!d.empty()) {
    pair<int, int> curr = d.front();
    d.pop_front();

    prev = temp;
    temp = arr[curr.first][curr.second];

    if(temp != prev) {
      answer++;
    }

    int a;
    a = iterate(curr.first + 1, curr.second, temp, visited, arr);
    if(a == 1) d.push_front({curr.first + 1, curr.second}); 
    else if(a == 0) d.push_back({curr.first + 1, curr.second}); 

    a = iterate(curr.first - 1, curr.second, temp, visited, arr);
    if(a == 1) d.push_front({curr.first - 1, curr.second}); 
    else if(a == 0) d.push_back({curr.first - 1, curr.second}); 

    a = iterate(curr.first, curr.second - 1, temp, visited, arr);
    if(a == 1) d.push_front({curr.first, curr.second - 1}); 
    else if(a == 0) d.push_back({curr.first, curr.second - 1}); 

    a = iterate(curr.first, curr.second + 1, temp, visited, arr);
    if(a == 1) d.push_front({curr.first, curr.second + 1}); 
    else if(a == 0) d.push_back({curr.first, curr.second + 1}); 
  }

  cout << answer << endl;


}

int main() {
    solve();  
}

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