Submission #640002

#	Time	Username	Problem	Language	Result	Execution time	Memory
640002		alextm	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1245 ms	123660 KiB

tracks

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

const int MAXN = 4001;

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

char mat[MAXN][MAXN];
int dist[MAXN][MAXN], n, m;

bool inside(int x, int y) {
  return (x >= 1 && x <= n && y >= 1 && y <= m && mat[x][y] != '.');
}

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

  deque<pair<int,int>> dq;
  dq.emplace_back(1, 1);
  dist[1][1] = 1;

  int answer = 1;
  while(!dq.empty()) {
    int l = dq.front().first;
    int c = dq.front().second;
    dq.pop_front();
    answer = max(answer, dist[l][c]);

    for(int k = 0; k < 4; k++) {
      int nxtl = l + dx[k];
      int nxtc = c + dy[k];
      if(inside(nxtl, nxtc) && !dist[nxtl][nxtc]) {
        if(mat[l][c] != mat[nxtl][nxtc]) { // weight 1
          dist[nxtl][nxtc] = dist[l][c] + 1;
          dq.emplace_back(nxtl, nxtc);
        } else {
          dist[nxtl][nxtc] = dist[l][c];
          dq.push_front({nxtl, nxtc});
        }
      }
    }
  }

  cout << answer << '\n';

  return 0;
}

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