Submission #1290756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290756		iemanuel	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1177 ms	173724 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>

const int nmax=4e3+2;
int mat[nmax][nmax];
bool visited[nmax][nmax];
int dist[nmax][nmax];
int n,m;

int di[]={-1,1,0,0};
int dj[]={0,0,-1,1};

bool inmat(int i,int j){
    return 1<=i&&i<=n&&1<=j&&j<=m;

}

void bfs1_0(int is,int js){
    deque<pii>q;
    q.push_front({is,js});
    visited[is][js]=1;
    dist[is][js]=1;
    while(!q.empty()){
        pii current=q.front();
        q.pop_front();

        for(int k=0;k<4;k++){
            int in=current.first+di[k];
            int jn=current.second+dj[k];
            if(inmat(in,jn)&&!visited[in][jn]&&mat[in][jn]){
                visited[in][jn]=1;

                if(mat[current.first][current.second]==mat[in][jn]){
                    q.push_front({in,jn});
                    dist[in][jn]=dist[current.first][current.second];
                }
                else{
                    q.push_back({in,jn});
                    dist[in][jn]=dist[current.first][current.second]+1;
                }
            }
        }
    }

}

void read(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char a;
            cin>>a;
            if(a=='.')mat[i][j]=0;
            if(a=='F')mat[i][j]=1;
            if(a=='R')mat[i][j]=2;
        }
    }



}


int main(){
    read();
    bfs1_0(1,1);
    int sol=-1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            sol=max(sol,dist[i][j]);
    }
    cout<<sol;


}

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