제출 #1095773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1095773		ezzzay	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1439 ms	493908 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ff first
#define ss second
#define pb push_back
const int N=4444;
char a[N][N];
bool vis[N][N];
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};
pair<int,int>par[N][N];
int lvl[N][N];
bool lvlvis[N*N];
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    queue<pair<int,int>>q,hq;
    q.push({n,m});
    int p=1;
    while(!(q.empty() and hq.empty())){
        int y,x;
        if(!q.empty()){
            y=q.front().ff,x=q.front().ss;
            q.pop();
            if(vis[y][x])continue;
        }
        else{
            while(!hq.empty()){
                y=hq.front().ff,x=hq.front().ss;
                hq.pop();
                if(vis[y][x]==0){
                    int py=par[y][x].ff,px=par[y][x].ss;
                    if(lvlvis[lvl[py][px]]==0)p++;
                    lvlvis[lvl[py][px]]=1;
                    break;
                }
                
            }
            if(vis[y][x])continue;
            
        }
        if(y==0 or x==0)continue;
        vis[y][x]=1;
        lvl[y][x]=p;
        char c=a[y][x];
        for(int i=0;i<4;i++){
            if(vis[y+yy[i]][x+xx[i]]==0){
                if(a[y+yy[i]][x+xx[i]]==c){
                    q.push({y+yy[i],x+xx[i]});
                }
                else if(a[y+yy[i]][x+xx[i]]=='F' or a[y+yy[i]][x+xx[i]]=='R'){
                    par[y+yy[i]][x+xx[i]]={y,x};
                    hq.push({y+yy[i],x+xx[i]});
                }
            }
        }
    }
    cout<<p;
}

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