제출 #880693

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

tracks

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

const int N = 4001;
int a[N][N];
int n, m;
int dx[4]={0, 0, 1, -1};
int dy[4]={1, -1, 0, 0};
bool mark[N][N];

int bfs(int x, int y){
    int ans=1;
    deque<pair<pair<int, int>, int>> q;
    q.push_back({{x, y}, 1});
    mark[x][y]=1;
    while(!q.empty()){
        pair<int, int> xy=q.front().F;
        ans=max(ans, q.front().S);
        q.pop_front();
        x=xy.F;
        y=xy.S;
        for(int i=0; i< 4; i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<m && !mark[nx][ny] && a[nx][ny]!=2){
                if(a[x][y]==a[nx][ny]){
                    q.push_front({{nx, ny}, ans});
                }
                else{
                    q.push_back({{nx, ny}, ans+1});
                }
                mark[nx][ny]=1;
            }
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i=0; i< n; i++){
        for(int j=0; j<m; j++){
            char c;
            cin >> c;
            if(c=='.')a[i][j]=2;
            else if(c=='R')a[i][j]=1;
        }
    }
    cout << bfs(0, 0);
}

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