제출 #418005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
418005		ilmar	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	827 ms	33948 KiB

tracks

#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;
}

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