제출 #810750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810750		serifefedartar	Tracks in the Snow (BOI13_tracks)	C++17	31.25 / 100	2120 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 1000005
 
const int delRow[] = {-1, 0, 0, 1};
const int delCol[] = {0, -1, 1, 0};
int H, W;
vector<string> grid;
queue<pair<int,int>> q, new_q;
int main() {
    fast
    cin >> H >> W;
 
    grid = vector<string>(H);
    for (int i = 0; i < H; i++)
        cin >> grid[i];
 
    vector<vector<int>> vis(H, vector<int>(W, false));
    q.push({0,0});
    int cnt = 1;
    while (!q.empty()) {
        pair<int,int> temp = q.front();
        q.pop();
        int row = temp.f;
        int col = temp.s;
 
        vis[row][col] = true;
        for (int i = 0; i < 4; i++) {
            int nRow = delRow[i] + row;
            int nCol = delCol[i] + col;
            if (nRow >= 0 && nCol >= 0 && nRow < H && nCol < W && !vis[nRow][nCol] && grid[nRow][nCol] != '.') {
                if (grid[nRow][nCol] == grid[row][col])
                    q.push({nRow, nCol});
                else
                    new_q.push({nRow, nCol});
            }
        }
 
        if (q.empty() && !new_q.empty()) {
            q = new_q;
            cnt++;
            new_q = queue<pair<int,int>>();
        }
    }
    cout << cnt << "\n";
}

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