Submission #581540

#	Time	Username	Problem	Language	Result	Execution time	Memory
581540		alexdd	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1554 ms	122036 KiB

tracks

#include<iostream>
#include<deque>
using namespace std;
int n,m;
char mat[4001][4001];
int dirlin[4]={1,-1,0,0};
int dircol[4]={0,0,1,-1};
deque<int> dqlin;
deque<int> dqcol;
int best[4001][4001];
bool good(int lin, int col)
{
    if(lin>=1 && lin<=n && col>=1 && col<=m)
        return 1;
    return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            {cin>>mat[i][j];best[i][j]=4000*4000+100;}
    dqlin.push_back(1);
    dqcol.push_back(1);
    best[1][1]=1;
    int lin,col;
    while(dqlin.empty()==0)
    {
        lin=dqlin.front();
        col=dqcol.front();
        dqlin.pop_front();
        dqcol.pop_front();
        for(int i=0;i<4;i++)
        {
            if(good(lin+dirlin[i], col+dircol[i]) && mat[lin+dirlin[i]][col+dircol[i]]!='.' && best[lin][col]+(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]])<best[lin+dirlin[i]][col+dircol[i]])
            {
                best[lin+dirlin[i]][col+dircol[i]]=best[lin][col]+(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]]);
                if(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]])
                {
                    dqlin.push_back(lin+dirlin[i]);
                    dqcol.push_back(col+dircol[i]);
                }
                else
                {
                    dqlin.push_front(lin+dirlin[i]);
                    dqcol.push_front(col+dircol[i]);

                }
            }
        }
    }
    int mxm=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            if(mat[i][j]!='.')
                mxm=max(mxm,best[i][j]);
    }
    cout<<mxm;
}

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