제출 #1289508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289508		bobtheguy	Tracks in the Snow (BOI13_tracks)	C++20	38.75 / 100	145 ms	85288 KiB

tracks

#include<bits/stdc++.h>
#define pll pair<long long,long long>
using namespace std;
 const long long dx[4]={1,-1,0,0};
 const long long dy[4]={0,0,-1,1};
 long long id[1010][1010],a[1010][1010],cnt=0,x,y,h,w,i,j;
 char c;
 vector<pll> adj[1000010];
 long long d[1000010];
 bool visited[1000010];
priority_queue<pll,vector<pll>,greater<pll>> pq;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>h>>w;
    for (i=1;i<=h;i++){
        for (j=1;j<=w;j++){
            cin>>c;
            if (c=='R') a[i][j]=1;
            else if (c=='F') a[i][j]=2;
            else a[i][j]=0;
            id[i][j]=++cnt;
        }
    }
    for (i=1;i<=h;i++){
        for (j=1;j<=w;j++){
            for (long long k=0;k<4;k++){
                x=dx[k]+i;y=dy[k]+j;
                if (x<0||y<0||x>h||y>w) continue;
                if (a[i][j]==0||a[x][y]==0) continue;
                if (a[i][j]==a[x][y]){
                    adj[id[i][j]].push_back({0,id[x][y]});
                    adj[id[x][y]].push_back({0,id[i][j]});
                }
                else{
                    adj[id[i][j]].push_back({1,id[x][y]});
                    adj[id[x][y]].push_back({1,id[i][j]});
                }
            }
        }
    }
    for (i=1;i<=h*w;i++) d[i]=1e18;
    d[1]=0;
    pq.push({0,1});
    while (!pq.empty()){
        long long u=pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u]=1;
        for (auto pr:adj[u]){
            long long w=pr.first,v=pr.second;
            if (d[v]>d[u]+w){
                d[v]=d[u]+w;
                pq.push({d[v],v});
            }
        }
    }
    long long ans=0;
    for (i=1;i<=h*w;i++){
        if (d[i]<1e18) ans=max(ans,d[i]);
    }
    cout<<ans+1;
}

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