제출 #1250510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1250510		d19n	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	563 ms	176032 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define inf __builtin_inf()

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

constexpr int N = 4e3 + 5;
char grid[N][N];
bool vis[N][N];

void solve(){
  int h, w; cin >> h >> w;

  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      cin >> grid[i][j];
    }
  }

  deque<tuple<int, int, int>> q;
  q.push_back({1, 0, 0});

  int mx = 1;

  while(sz(q)) {
    const auto [cost, i, j] = q.front();
    q.pop_front();
    if(vis[i][j]) continue;
    
    vis[i][j] = true;
    mx = max(mx, cost);
    
    for(int k = 0; k < 4; k++){
      int y = dy[k] + i, x = dx[k] + j;
      if(y < 0 || x < 0 || y == h || x == w || vis[y][x] || grid[y][x] == '.') continue;

      if(grid[y][x] != grid[i][j]){
        q.push_back({cost + 1, y, x});
      } else {
        q.push_front({cost, y, x});
      }
    }
  } 

  cout << mx;
}

int main(){
  ios_base::sync_with_stdio(false), cin.tie(NULL);
  // int t; cin >> t; while(t--)
  solve(), cout << '\n';
  return 0;
}

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