Submission #1000421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000421		AlgorithmWarrior	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	921 ms	120672 KiB

tracks

#include <bits/stdc++.h>
#define MAX 4005
#define PII pair<int,int>

using namespace std;

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

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;
    deque<PII>deq;
    deq.push_front({1,1});
    while(!deq.empty())
    {
        PII nou=deq.front();
        int l=nou.first;
        int c=nou.second;
        deq.pop_front();
        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(mat[l][c]==mat[lnou][cnou])
                    deq.push_front({lnou,cnou});
                else
                    deq.push_back({lnou,cnou});
            }
        }
    }
    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: 70 / 70