Submission #1218308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218308		Cyanberry	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1637 ms	35968 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<pair<int, int>> bfs, nex;
    vector<vector<bool>> visited(h, vector<bool>(w, false));
    bfs.push({0, 0});
    while (!bfs.empty()) {
        pair<int, int> curr = bfs.front();
        bfs.pop();
        if (!visited[curr.first][curr.second]) {
            visited[curr.first][curr.second] = true;
            for (vector<int> move : moves) {
            int nx = curr.first + move[0];
                int ny = curr.second + 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.first][curr.second]) bfs.push({nx, ny});
                else nex.push({nx, ny});
            }
        }
        
        
        if (bfs.empty()) {
            // cout<<curr.first<<' '<<curr.second<<'\n';
            swap(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: 70 / 70