Submission #1000416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000416		AlgorithmWarrior	Tracks in the Snow (BOI13_tracks)	C++14	78.13 / 100	2094 ms	94804 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};

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;
    queue<pair<int,int>>q;
    q.push({1,1});
    inqueue[1][1]=1;
    while(!q.empty())
    {
        pair<int,int>nou=q.front();
        int l=nou.first;
        int c=nou.second;
        q.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])
                {
                    q.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: 48.125 / 70