제출 #1026631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026631		kkkkkkkk	Tracks in the Snow (BOI13_tracks)	C++14	82.50 / 100	2083 ms	105260 KiB

tracks

#include <bits/stdc++.h>
 
using namespace std;
 
int dr[]={+1, 0, -1, 0};
int dc[]={0, +1, 0, -1};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    char tracks[n][m];
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            cin >> tracks[i][j];
    priority_queue<pair<int, pair<int,int> > > pq;
    pq.push({-1, {0,0}});
    int vis[n][m], rez=1;
    memset(vis, -1, sizeof(vis));
    while (!pq.empty()) {
        int r=pq.top().second.first, c=pq.top().second.second, dist=-pq.top().first;
        pq.pop();
        if (vis[r][c]!=-1) continue;
        vis[r][c]=dist;
        rez=max(rez, dist);
        for (int i=0;i<4;i++) {
            int nr=r+dr[i], nc=c+dc[i];
            if (nr>=0&&nc>=0&&nr<n&&nc<m&&tracks[nr][nc]!='.') {
                if (tracks[nr][nc]!=tracks[r][c]) pq.push({-(dist+1), {nr, nc}});
                else pq.push({-dist, {nr, nc}});
            }
        }
    }
    cout << rez;
 
    return 0;
}

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