Submission #959440

#	Time	Username	Problem	Language	Result	Execution time	Memory
959440		AtinaR	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1149 ms	252236 KiB

tracks

#include <bits/stdc++.h>

using namespace std;
const long long MAX=4001;
long long n,m;
char mat[MAX][MAX];
long long di[4]={0,0,-1,1};
long long dj[4]={1,-1,0,0};
long long vis[MAX][MAX];
bool valid_move(long long i, long long j)
{
    if(i<0 || i>=n || j<0 || j>=m || vis[i][j]!=0 || mat[i][j]=='.')return false;
    return true;
}
int main()
{
    cin>>n>>m;
    for(long long i=0; i<n; i++)
    {
        for(long long j=0; j<m; j++)
        {
            cin>>mat[i][j];
        }
    }
    deque<pair<long long,long long> > q;
    long long res=0;
    q.push_back({0,0});
    memset(vis,0,sizeof(vis));
    vis[0][0]=1;
    while(q.size())
    {
        pair<long long,long long> curr=q.front();
        q.pop_front();
        res=max(res,vis[curr.first][curr.second]);
        for(long long k=0; k<4; k++)
        {
            long long newi=curr.first+di[k];
            long long newj=curr.second+dj[k];
            if(!valid_move(newi,newj))continue;
            if(mat[newi][newj]==mat[curr.first][curr.second])
            {
                q.push_front({newi,newj});
                vis[newi][newj]=vis[curr.first][curr.second];
            }
            else
            {
                 q.push_back({newi,newj});
                 vis[newi][newj]=vis[curr.first][curr.second]+1;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}
/*
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF*/

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