Submission #1093075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093075		mm77	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	857 ms	144928 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
const int N=4e3+3;
char t[N][N];
int dp[N][N];
bool odw[N][N];
deque<pair<int,int>>Q;
int n,m;
bool ok(int a,int b)
{
    if(a>n||a<1||b>m||b<1||t[a][b]=='.')return false;
    return true;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>t[i][j];
        }
    }
    dp[1][1]=1;
    Q.push_back({1,1});
    int res=1;
    while(!Q.empty())
    {
        int x=Q.front().first,y=Q.front().second;
        Q.pop_front();

        res=max(dp[x][y],res);
        odw[x][y]=true;
        if(!odw[x-1][y]&&ok(x-1,y))
        {
            odw[x-1][y]=true;
            if(t[x-1][y]==t[x][y])
            {
                dp[x-1][y]=dp[x][y];
                Q.push_front({x-1,y});
            }
            else
            {
                dp[x-1][y]=dp[x][y]+1;
                Q.push_back({x-1,y});
            }
        }
        if(!odw[x+1][y]&&ok(x+1,y))
        {
            odw[x+1][y]=true;
            if(t[x+1][y]==t[x][y])
            {
                dp[x+1][y]=dp[x][y];
                Q.push_front({x+1,y});
            }
            else
            {
                dp[x+1][y]=dp[x][y]+1;
                Q.push_back({x+1,y});
            }
        }
        if(!odw[x][y-1]&&ok(x,y-1))
        {
            odw[x][y-1]=true;
            if(t[x][y-1]==t[x][y])
            {
                dp[x][y-1]=dp[x][y];
                Q.push_front({x,y-1});
            }
            else
            {
                dp[x][y-1]=dp[x][y]+1;
                Q.push_back({x,y-1});
            }
        }
        if(!odw[x][y+1]&&ok(x,y+1))
        {
            odw[x][y+1]=true;
            if(t[x][y+1]==t[x][y])
            {
                dp[x][y+1]=dp[x][y];
                Q.push_front({x,y+1});
            }
            else
            {
                dp[x][y+1]=dp[x][y]+1;
                Q.push_back({x,y+1});
            }
        }
    }
    cout<<res<<"\n";
    return 0;
}

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