Submission #770757

#	Time	Username	Problem	Language	Result	Execution time	Memory
770757		xCqlibur	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	23 ms	3048 KiB

tracks

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

#define ll long long

const int mxH=505, mxW=505;

int H, W;

char grid[mxH][mxW], rChange[4]={0, 1, 0, -1}, cChange[4]={1, 0, -1, 0};
bool vis[mxH][mxW];
vector<pair<int, int>> dir;

void floodfill(int r, int c, char curr) {
    stack<pair<int, int>> frontier;
    frontier.push({r, c});
    while(!frontier.empty()) {
        r=frontier.top().first;
        c=frontier.top().second;
        frontier.pop();
        if(r<0||r>=H||c<0||c>=W||vis[r][c]) {
            continue;
        }
        if(grid[r][c]!=curr&&grid[r][c]!='.') {
            dir.push_back({r, c});
            continue;
        }
        for(int i=0; i<4; ++i) {
            if(vis[r+rChange[i]][c+cChange[i]])
                continue;
            vis[r+rChange[i]][c+cChange[i]]=1;
            frontier.push({r+rChange[i], c+cChange[i]});
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> H >> W;
    for(int i=0; i<H; ++i) {
        for(int j=0; j<W; ++j) {
            cin >> grid[i][j];
        }
    }
    vis[0][0]=1;
    int ans=0;
    dir.push_back({0, 0});
    while(1) {
        if(dir.empty())
            break;
        for(pair<int, int> p : dir) {
            floodfill(p.first, p.second, grid[p.first][p.second]);
            dir.erase(remove(dir.begin(), dir.end(), p), dir.end());
        }
        ++ans;
    }
    cout << ans+1;
}

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