Submission #418005

#TimeUsernameProblemLanguageResultExecution timeMemory
418005ilmarTracks in the Snow (BOI13_tracks)C++17
2.19 / 100
827 ms33948 KiB
#include <bits/stdc++.h>
using namespace std;

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

	int h, w;
    cin >> h >> w;
    vector<vector<char>> grid(h, vector<char>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> grid[i][j];
        }
    }

    int ans = 0;
    bool done = false;
    char last = grid[0][0];
    queue<pair<int, int>> q;
    vector<vector<bool>> vis(h, vector<bool>(w, false));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (!vis[i][j] && grid[i][j] != '.') {
                q.push({i, j});
                vis[i][j] = true;
                if (grid[i][j] == last)
                    ans++;
                else if (!done) {
                    ans++;
                    done = true;
                }
            }
            while (!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                
                if (x + 1 < h && grid[x + 1][y] == grid[i][j] && !vis[x + 1][y]) {
                    vis[x + 1][y] = true;
                    q.push({x + 1, y});
                }
                if (x - 1 >= 0 && grid[x - 1][y] == grid[i][j] && !vis[x - 1][y]) {
                    vis[x - 1][y] = true;                
                    q.push({x - 1, y});
                }

                if (y + 1 < w && grid[x][y + 1] == grid[i][j] && !vis[x][y + 1]) {
                    vis[x][y + 1] = true;
                    q.push({x, y + 1});
                }
                if (y - 1 >= 0 && grid[x][y - 1] == grid[i][j] && !vis[x][y - 1]) {
                    vis[x][y - 1] = true;
                    q.push({x, y - 1});
                }
            }
        }
    }

    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...