제출 #1121136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121136		AtabayRajabli	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	901 ms	88828 KiB

tracks

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

const int sz = 4e3 + 5;
int n, m, used[sz][sz];
char c[sz][sz];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> c[i][j];

    int ans = 0, cur = 0;
    queue<array<int, 2>> q[2];
    q[cur].push({0, 0});
    used[0][0] = 1;

    while(!q[cur].empty())
    {
        ans++;
        assert(ans < n * m);
        while(!q[cur].empty())
        {
            int x = q[cur].front()[0], y = q[cur].front()[1];
            q[cur].pop();
            for(int i = 0; i < 4; i++)
            {
                int nx = x + dx[i], ny = y + dy[i];
                if(nx < 0 || n <= nx || ny < 0 || m <= ny || used[nx][ny] || c[nx][ny] == '.') continue;
                if(c[nx][ny] == c[x][y]) q[cur].push({nx, ny});
                else q[!cur].push({nx, ny});
                used[nx][ny] = 1;
            }
        }
        cur = !cur;
    }
    cout << ans << '\n';
}  

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