Submission #1020592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020592		NguyenPhucThang	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	643 ms	139108 KiB

tracks

#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int base = 31;
const ll mod = 1e9 + 7;
const ll oo = 1e18;
const int N = 4005;

char a[N][N];
int d[N][N];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   int m, n;
   cin >> m >> n;
   forr(i, 1, m) forr(j, 1, n) cin >> a[i][j];

   memset(d, 63, sizeof d);

   deque<pii> dq;
   dq.push_back({1, 1});

   d[1][1] = 1;

   int res = 0;

   while (!dq.empty()){
      pii u = dq.front();
      dq.pop_front();
      res = max(res, d[u.fi][u.se]);
      forr(i, 0, 3){
         int x = u.fi + dx[i], y = u.se + dy[i];
         if (1 <= x && x <= m && 1 <= y && y <= n && a[x][y] != '.'){
            if (d[u.fi][u.se] < d[x][y] && a[u.fi][u.se] == a[x][y]){
               dq.push_front({x, y});
               d[x][y] = d[u.fi][u.se];
            } 
            else if (d[u.fi][u.se] + 1 < d[x][y] && a[u.fi][u.se] != a[x][y]){
               dq.push_back({x, y});
               d[x][y] = d[u.fi][u.se] + 1;
            }
         }
      }
   }  
   
   cout << res;

   return 0;
}

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