제출 #1081713

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

tracks

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

#undef _GLIBCXX_DEBUG

#define rep(i, a, b) for(ll i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

vector<vector<char>> grid;
ll visited[4010][4010];
ll H, W;
vector<pair<ll,ll>> q;
vector<pair<ll,ll>> q2;

ll dfs(ll row, ll col, char curr){
    if (row >= H || col >= W || col < 0 || row <0) return 0;
    if (visited[row][col] == 1) return 0;
    if (grid[row][col] =='.') return 0;
    if (grid[row][col] != curr){
        q2.push_back(make_pair(row,col));
        //cout << "in bfs " << row << " " << col << "\n";
        return 0;
    }
    visited[row][col] = 1;
    
    dfs(row+1, col,curr);
    dfs(row-1, col,curr);
    dfs(row, col+1,curr);
    dfs(row, col-1,curr);
    return 0;
}

int main(){
    //cin.tie(0)->sync_with_stdio(0);
    memset(visited, 0, sizeof(visited));
    cin >>H >> W;
    grid.resize(H, vector<char>(W));
    char temp;
    rep(i,0,H)
        rep (j,0,W){
            cin >> temp;
            grid[i][j] = temp;
        }
    char ani = grid[0][0];


    q.push_back(make_pair(0,0));
    
    
    ll cnt =0;
    while (q.size()){
        

        while(!q.empty()){
            pll s = q.back();
            q.pop_back();

            dfs(s.first, s.second, grid[s.first][s.second]);
            


        }
        //cout << "new q " << "\n";
        cnt ++;
        swap(q, q2);
        q2.clear();
        if (ani == 'R') ani = 'F';
        if (ani == 'F') ani = 'R';
    }
    cout << cnt << "\n";
    return 0;
}

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