Submission #1000418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000418		AlgorithmWarrior	Tracks in the Snow (BOI13_tracks)	C++14	84.69 / 100	2080 ms	168460 KiB

tracks

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

using namespace std;

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

struct str
{
    int lin,col,val;
};

class cmp
{
public:
    bool operator()(str a,str b)
    {
        return bfs[a.lin][a.col]>bfs[b.lin][b.col];
    }
};

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<str,vector<str>,cmp>pq;
    pq.push({1,1,1});
    while(!pq.empty())
    {
        str nou=pq.top();
        int l=nou.lin;
        int c=nou.col;
        int v=nou.val;
        pq.pop();
        if(v>bfs[l][c])
            continue;
        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;
                pq.push({lnou,cnou,pret});
            }
        }
    }
    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