제출 #1193724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193724		Hamed_Ghaffari	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	489 ms	119076 KiB

tracks

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

using pii = pair<int, int>;

#define X               first
#define Y               second

const int MXN = 4001;

int n, m;
char a[MXN][MXN];
int dis[MXN][MXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin >> a[i][j],
            dis[i][j] = -1;
    deque<pii> dq;
    dq.push_back({0, 0});
    dis[0][0] = 1;
    while(!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        for(int d=0, xx, yy; d<4; d++) {
            xx = x + dx[d], yy = y + dy[d];
            if(xx<0 || xx>=n || yy<0 || yy>=m || a[xx][yy]=='.' || dis[xx][yy]!=-1) continue;
            if(a[x][y]==a[xx][yy]) {
                dis[xx][yy] = dis[x][y];
                dq.push_front({xx, yy});
            }
            else {
                dis[xx][yy] = dis[x][y]+1;
                dq.push_back({xx, yy});
            }
        }
    }
    int ans=0;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if(a[i][j]!='.')
                ans = max(ans, dis[i][j]);
    cout << ans << '\n';
    return 0;
}

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