Submission #1227760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227760		vyaduct	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	987 ms	141328 KiB

tracks

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

/* Somehow, we just link connected componants together
 * and find max distance to (1,1)
*/

const int mxN = 4000;
int a[mxN][mxN];
bool visited[mxN][mxN];
int d[mxN][mxN];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool valid(int x, int y, int n, int m){
  return x >= 0 && x < n && y >= 0 && y < m;
}

void solve(){
  int n,m; cin>>n>>m;
  for (int i=0;i<n;i++){
    for (int j=0;j<m;j++){
      char c; cin>>c;
      visited[i][j] = false;
      if (c == '.') a[i][j] = 0;
      else if (c == 'F') a[i][j] = 1;
      else a[i][j] = 2;
    }
  }

  pair<int,int> s = {0,0};
  queue<pair<int,int>> q;
  d[s.first][s.second] = 0;
  visited[s.first][s.second] = true;
  q.push(s);
  int ans = 0;
  while(!q.empty()){
    pair<int,int> cur = q.front(); q.pop();
    ans = max(ans, d[cur.first][cur.second]);
    for (int k=0;k<4;k++){
      int r = cur.first + dx[k], c = cur.second + dy[k];
      if (valid(r, c, n, m)){
        if (!visited[r][c]){
          if (a[r][c] == a[cur.first][cur.second]){
            d[r][c] = d[cur.first][cur.second];
          } else {
            d[r][c] = d[cur.first][cur.second]+1;
          }
          visited[r][c] = true;
          q.push(make_pair(r,c));
        }
      }
    }
  }
  cout << ans << endl;
}

int main(){
  solve();
  return 0;
}

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