제출 #810712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810712		serifefedartar	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	2136 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 1000005

const int delRow[] = {-1, 0, 0, 1};
const int delCol[] = {0, -1, 1, 0};
int H, W;
vector<vector<int>> grid;
queue<pair<int,int>> q, new_q;
int main() {
    fast
    cin >> H >> W;

    grid = vector<vector<int>>(H+1, vector<int>(W+1));
    for (int i = 1; i <= H; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= W; j++) {
            if (s[j-1] == '.')
                grid[i][j] = -1;
            else if (s[j-1] == 'F')
                grid[i][j] = 0;
            else
                grid[i][j] = 1;
        }
    }

    vector<vector<int>> vis(H+1, vector<int>(W+1, false));
    q.push({1,1});
    int cnt = 1;
    while (!q.empty()) {
        if (cnt % 2) {
            int row = q.front().f;
            int col = q.front().s;
            q.pop();

            vis[row][col] = true;
            for (int i = 0; i < 4; i++) {
                int nRow = delRow[i] + row;
                int nCol = delCol[i] + col;
                if (nRow >= 1 && nCol >= 1 && nRow <= H && nCol <= W && !vis[nRow][nCol] && grid[nRow][nCol] != -1) {
                    if (grid[nRow][nCol] == grid[row][col])
                        q.push({nRow, nCol});
                    else
                        new_q.push({nRow, nCol});
                }
            }
            if (q.empty() && !new_q.empty())
                cnt++;
        } else {
            int row = new_q.front().f;
            int col = new_q.front().s;
            new_q.pop();

            vis[row][col] = true;
            for (int i = 0; i < 4; i++) {
                int nRow = delRow[i] + row;
                int nCol = delCol[i] + col;
                if (nRow >= 1 && nCol >= 1 && nRow <= H && nCol <= W && !vis[nRow][nCol] && grid[nRow][nCol] != -1) {
                    if (grid[nRow][nCol] == grid[row][col])
                        new_q.push({nRow, nCol});
                    else
                        q.push({nRow, nCol});
                }
            }

            if (!q.empty() && new_q.empty())
                cnt++;
        }
    }
    cout << cnt << "\n";
}

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