Submission #1168694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168694		I_FloPPed21	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	747 ms	176096 KiB

tracks

#include <iostream>
#include <deque>
using namespace std;
const int N=4001;
char mat[N][N];
bool viz[N][N];
int n,m;
int ans=0;
struct coada
{
    int x,y,val;
};
int dx[]={1,0,-1,0};
int dy[]={0,-1,0,1};
bool inmat(int i,int j)
{
    return(i<=n&&i>=1&&j<=m&&j>=1);
}
deque<coada>dq;
void citeste()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cin>>mat[i][j];
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int test;
    citeste();
    dq.push_front({1,1,1});
    while(!dq.empty())
    {
        int x=dq.front().x;
        int y=dq.front().y;
        int val=dq.front().val;
        dq.pop_front();
         if(viz[x][y])
            continue;
        viz[x][y]=true;
        ans=max(val,ans);
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i];
            int b=y+dy[i];
            if(!inmat(a,b))
                continue;
            if(mat[a][b]=='.')
                continue;
            if(viz[a][b])
                continue;
            if(mat[a][b]!=mat[x][y])
            dq.push_back({a,b,val+1});
            else
            dq.push_front({a,b,val});
        }
    }
    cout<<ans;

    return 0;
}

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