제출 #1185150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185150		Godgift42	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	625 ms	146812 KiB

tracks

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

int main(){
    int h,w;
    cin >> h >> w;
    vector<vector<int>> gr(h,vector<int>(w));
    for(int i=0;i<h;i++){
        string s;
        cin >> s;
        for(int j=0;j<w;j++){
            if(s[j]=='R')gr[i][j]=1;
            else if(s[j]=='F')gr[i][j]=-1;
        }
    }
    deque<pair<int,int>> dq;
    vector<vector<int>> dist(h,vector<int>(w));
    dist[0][0]=1;
    dq.push_front({0,0});
    int ans=1;
    while(!dq.empty()){
        auto [i,j]=dq.front();
        dq.pop_front();
        ans=max(ans,dist[i][j]);
        if(i>0 and dist[i-1][j]==0){
            if(gr[i-1][j]==gr[i][j]){
                dq.push_front({i-1,j});
                dist[i-1][j]=dist[i][j];
            }
            else if(gr[i-1][j]*(-1)==gr[i][j]){
                dq.push_back({i-1,j});
                dist[i-1][j]=dist[i][j]+1;
            }
        }
        if(i<h-1 and dist[i+1][j]==0){
            if(gr[i+1][j]==gr[i][j]){
                dq.push_front({i+1,j});
                dist[i+1][j]=dist[i][j];
            }
            else if(gr[i+1][j]*(-1)==gr[i][j]){
                dq.push_back({i+1,j});
                dist[i+1][j]=dist[i][j]+1;
            }
        }
        if(j>0 and dist[i][j-1]==0){
            if(gr[i][j]==gr[i][j-1]){
                dq.push_front({i,j-1});
                dist[i][j-1]=dist[i][j];
            }
            else if(gr[i][j-1]*(-1)==gr[i][j]){
                dq.push_back({i,j-1});
                dist[i][j-1]=dist[i][j]+1;
            }
        }
        if(j<w-1 and dist[i][j+1]==0){
            if(gr[i][j]==gr[i][j+1]){
                dq.push_front({i,j+1});
                dist[i][j+1]=dist[i][j];
            }
            else if(gr[i][j+1]*(-1)==gr[i][j]){
                dq.push_back({i,j+1});
                dist[i][j+1]=dist[i][j]+1;
            }
        }
    }
    cout << ans << "\n";
}

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