제출 #1218306

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218306		Cyanberry	Tracks in the Snow (BOI13_tracks)	C++17	84.69 / 100	2099 ms	216232 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;

vector<vector<int>> moves = {
    {-1, 0},
    {1, 0},
    {0, -1},
    {0, 1},
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    string e;
    vector<string> grid;
    cin>>h>>w;
    for (int i = 0; i < h; ++i) {
        cin>>e;
        grid.push_back(e);
    }
    int ret = 0;
    queue<vector<int>> bfs, nex;
    vector<vector<bool>> visited(h, vector<bool>(w, false));
    bfs.push({0, 0});
    while (!bfs.empty()) {
        vector<int> curr = bfs.front();
        
        bfs.pop();
        
        if (!visited[curr[0]][curr[1]]) 
        for (vector<int> move : moves) {
            int nx = curr[0] + move[0];
            int ny = curr[1] + move[1];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
                continue;
            }
            if (visited[nx][ny]) continue;
            if (grid[nx][ny] == '.') continue;
            if (grid[nx][ny] == grid[curr[0]][curr[1]]) bfs.push({nx, ny});
            else nex.push({nx, ny});
        }
        visited[curr[0]][curr[1]] = true;
        if (bfs.empty()) {
            // cout<<curr[0]<<' '<<curr[1]<<'\n';
            bfs = nex;
            while(!nex.empty()) nex.pop();
            ++ret;
        }
    }
    // if (h == 5 && w == 8 && ret == 2) while(true) ++h;
    cout<<ret;
}

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