제출 #1310962

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

tracks

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

struct trio{
    int val, x, y;
    bool operator < (const trio& other)const{
        return val < other.val;
    }
};


const int N = 4003;
const vector<pii> DIR = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char tab[N][N];
int dist[N][N];
bool vis[N][N];
priority_queue<trio> pq;

void solve(){
    vis[1][1] = 1;
    pq.push({0, 1, 1});
    int x, y, xp, yp;
    while(!pq.empty()){
        x = pq.top().x;
        y = pq.top().y;
        pq.pop();
        for(auto p : DIR){
            xp = x + p.first;
            yp = y + p.second;
            if(vis[xp][yp]) continue;
            if(tab[x][y] == tab[xp][yp]){
                pq.push({-dist[x][y], xp, yp});
                dist[xp][yp] = dist[x][y];
                vis[xp][yp] = 1;
            }else if(tab[xp][yp] == 'F' || tab[xp][yp] == 'R'){
                dist[xp][yp] = dist[x][y] + 1;
                vis[xp][yp] = 1;
                pq.push({-dist[xp][yp], xp, yp});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    for(int i = 1 ; i <= h ; i++){
        for(int j = 1 ; j <= w ; j++){
            cin >> tab[i][j];
        }
    }
    solve();
    int ans = 0;
    for(int i = 1 ; i <= h ; i++){
        for(int j = 1 ; j <= w ; j++){
            ans = max(ans, dist[i][j]);
        }
    }
    cout << ans + 1 << '\n';
}

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