Submission #862324

#	Time	Username	Problem	Language	Result	Execution time	Memory
862324		8pete8	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1090 ms	222024 KiB

tracks

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiii pair<pii,pii>
#define ppii pair<pii,pii>
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
const int mxn=5e5+10,mx=5e6+10,minf=-1e9;
bool vis[4004][4004];
int u[4]={0,0,1,-1};
int r[4]={1,-1,0,0},n,m;
int grid[4004][4004];
int32_t main(){
    fastio
    deque<ppii>dq;
    cin>>n>>m;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){
        char a;cin>>a;
        if(a=='.')grid[i][j]=-1;
        else if(a=='F')grid[i][j]=1;
    }
    int ans=0;
    dq.push_front({{grid[0][0],1},{0,0}});//
    while(!dq.empty()){
        int cc=dq.front().f.f,c=dq.front().f.s,cx=dq.front().s.f,cy=dq.front().s.s;
        ans=max(ans,c);
        dq.pop_front();
        vis[cx][cy]=true;
        for(int i=0;i<4;i++){
            int nx=cx+u[i],ny=cy+r[i];
            if(nx<0||nx>=n||ny<0||ny>=m)continue;
            if(vis[nx][ny])continue;
            if(grid[nx][ny]==-1)continue;
            if(grid[nx][ny]!=cc)dq.push_back({{1-cc,c+1},{nx,ny}});
            else dq.push_front({{cc,c},{nx,ny}});
        }
    }
    cout<<ans<<'\n';
}

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