제출 #1000417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1000417		AlgorithmWarrior	Tracks in the Snow (BOI13_tracks)	C++14	84.69 / 100	2081 ms	149872 KiB

tracks

#include <bits/stdc++.h>
#define MAX 4005

using namespace std;

char mat[MAX][MAX];
int bfs[MAX][MAX];
bool inqueue[MAX][MAX];
int dl[]={-1,0,1,0};
int dc[]={0,1,0,-1};

class cmp
{
public:
    bool operator()(pair<int,int> a,pair<int,int> b)
    {
        return bfs[a.first][a.second]>bfs[b.first][b.second];
    }
};

int main()
{
    int n,m;
    cin>>n>>m;
    int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {
            cin>>mat[i][j];
            bfs[i][j]=INT_MAX;
        }
    bfs[1][1]=1;
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>pq;
    pq.push({1,1});
    inqueue[1][1]=1;
    while(!pq.empty())
    {
        pair<int,int>nou=pq.top();
        int l=nou.first;
        int c=nou.second;
        pq.pop();
        inqueue[l][c]=0;
        for(i=0;i<4;++i)
        {
            int lnou=l+dl[i];
            int cnou=c+dc[i];
            int pret=bfs[l][c]+(mat[l][c]!=mat[lnou][cnou]);
            if(isalpha(mat[lnou][cnou]) && pret<bfs[lnou][cnou])
            {
                bfs[lnou][cnou]=pret;
                if(!inqueue[lnou][cnou])
                {
                    pq.push({lnou,cnou});
                    inqueue[lnou][cnou]=1;
                }
            }
        }
    }
    int answer=-1;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(isalpha(mat[i][j]))
                answer=max(answer,bfs[i][j]);
    cout<<answer;
    return 0;
}

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