제출 #1120877

#제출 시각아이디문제언어결과실행 시간메모리
1120877vjudge1Tracks in the Snow (BOI13_tracks)C++17
97.81 / 100
1663 ms1048576 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<char>> grid(4500,vector<char>(4500));
vector<vector<bool>> vis(4500,vector<bool>(4500,0));
vector<int> dx = {1,0,-1,0};
vector<int> dy = {0,1,0,-1};
int n,m;
int cnt=0;
void dfs(int i,int j,vector<pair<int,int>> &yolla){
    vis[i][j] = 1;
    for(int ind =0;ind < 4;++ind){
        int x = i + dx[ind];
        int y = j + dy[ind];
        if(x > n || x == 0 || y > m || y == 0){
            continue;
        }
        if(grid[x][y] == '.')continue;
        if(vis[x][y])continue;
        if(grid[x][y] != grid[i][j]){
            yolla.push_back({x,y});
        }else dfs(x,y,yolla);
    }
}
signed main(){
    cin >> n >> m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin >> grid[i][j];
        }
    }
    vector<pair<int,int>> nextt,nextt2,emptyy;
    dfs(1,1,nextt);
    int curr=1;
    while(!nextt.empty()){
        curr++;
        nextt2.clear();
        while(!nextt.empty()){
            auto &[x,y] = nextt.back();
            nextt.pop_back();
            dfs(x,y,nextt2);
        }
        nextt = nextt2;
    }
    cout << curr;
}
//3  2 
// FFRF....
// .FRRR...
// .FFFFF..
// ..RRRFFR
// .....FFF
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...