제출 #880557

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

tracks

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
//const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second

queue<pair<int,int>>fq,rq;
bool vis[4000][4000];
string arr[4000];
int w,h;

void t(int x,int y){
    if(x<0||x>=w||y<0||y>=h)
        return;
    if(vis[x][y])
        return;
    vis[x][y]=true;
    if(arr[y][x]=='F')
        fq.push({x,y});
    if(arr[y][x]=='R')
        rq.push({x,y});
}

void solve(){
    cin>>h>>w;
    for(int i=0;i<h;i++)
        cin>>arr[i];
    
    bool is_f=arr[0][0]=='F';
    vis[0][0]=true;
    if(is_f)
        fq.push({0,0});
    else
        rq.push({0,0});
    
    int res=0;
    while(true){
        if(is_f){
            if(fq.empty())
                break;
            
            while(!fq.empty()){
                auto curr=fq.front();
                fq.pop();
                t(curr.first-1,curr.second);
                t(curr.first+1,curr.second);
                t(curr.first,curr.second-1);
                t(curr.first,curr.second+1);
            }
            
        }else{
            if(rq.empty())
                break;
            
            while(!rq.empty()){
                auto curr=rq.front();
                rq.pop();
                t(curr.first-1,curr.second);
                t(curr.first+1,curr.second);
                t(curr.first,curr.second-1);
                t(curr.first,curr.second+1);
            }
        }
        is_f=!is_f;
        res++;
    }
    cout<<res<<"\n";
}

int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("bank.in","r",stdin);freopen("bank.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}

/*
 
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
 
 */

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