답안 #875565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875565	2023-11-20T04:05:32 Z	12345678	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	708 ms	57424 KB

tracks

#include <bits/stdc++.h>

using namespace std;

const int N=4e3+5;
int h, w, cnt, dx[4]={1, 0, 0, -1}, dy[4]={0, 1, -1, 0};
char mp[N][N], c;
queue<pair<int, int>> q, nq;
bool vs[N][N];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>h>>w;
    for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) cin>>mp[i][j];
    nq.push({1, 1});
    vs[1][1]=1;
    while (!nq.empty())
    {
        cnt++;
        c=mp[nq.front().first][nq.front().second];
        while (!nq.empty()) q.push(nq.front()), nq.pop();
        while (!q.empty())
        {
            auto [x, y]=q.front();
            //cout<<cnt<<' '<<x<<' '<<y<<' '<<c<<'\n';
            q.pop();
            for (int i=0; i<4; i++)
            {
                int nx=x+dx[i], ny=y+dy[i];
                if (nx<1||nx>h||ny<1||ny>w||mp[nx][ny]=='.'||vs[nx][ny]) continue;
                vs[nx][ny]=1;
                if (mp[nx][ny]==c) q.push({nx, ny});
                else nq.push({nx, ny});
            }
        }
    }
    cout<<cnt;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	6748 KB	Output is correct
2	Correct	2 ms	2396 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	9 ms	6752 KB	Output is correct
5	Correct	3 ms	5724 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2652 KB	Output is correct
8	Correct	1 ms	2652 KB	Output is correct
9	Correct	1 ms	2904 KB	Output is correct
10	Correct	3 ms	5464 KB	Output is correct
11	Correct	2 ms	3160 KB	Output is correct
12	Correct	5 ms	5724 KB	Output is correct
13	Correct	3 ms	5724 KB	Output is correct
14	Correct	3 ms	5708 KB	Output is correct
15	Correct	12 ms	6744 KB	Output is correct
16	Correct	11 ms	6748 KB	Output is correct
17	Correct	8 ms	6696 KB	Output is correct
18	Correct	6 ms	6744 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	31572 KB	Output is correct
2	Correct	42 ms	12892 KB	Output is correct
3	Correct	268 ms	46940 KB	Output is correct
4	Correct	68 ms	21584 KB	Output is correct
5	Correct	167 ms	35152 KB	Output is correct
6	Correct	708 ms	57424 KB	Output is correct
7	Correct	10 ms	31832 KB	Output is correct
8	Correct	9 ms	31324 KB	Output is correct
9	Correct	2 ms	2536 KB	Output is correct
10	Correct	1 ms	2392 KB	Output is correct
11	Correct	10 ms	31468 KB	Output is correct
12	Correct	1 ms	2904 KB	Output is correct
13	Correct	48 ms	12880 KB	Output is correct
14	Correct	24 ms	10844 KB	Output is correct
15	Correct	18 ms	11520 KB	Output is correct
16	Correct	20 ms	6792 KB	Output is correct
17	Correct	109 ms	22596 KB	Output is correct
18	Correct	82 ms	22356 KB	Output is correct
19	Correct	64 ms	21584 KB	Output is correct
20	Correct	61 ms	18876 KB	Output is correct
21	Correct	155 ms	35896 KB	Output is correct
22	Correct	176 ms	35128 KB	Output is correct
23	Correct	219 ms	30020 KB	Output is correct
24	Correct	169 ms	35776 KB	Output is correct
25	Correct	366 ms	46908 KB	Output is correct
26	Correct	367 ms	42256 KB	Output is correct
27	Correct	474 ms	48472 KB	Output is correct
28	Correct	671 ms	57144 KB	Output is correct
29	Correct	634 ms	55488 KB	Output is correct
30	Correct	563 ms	53876 KB	Output is correct
31	Correct	506 ms	37200 KB	Output is correct
32	Correct	485 ms	48060 KB	Output is correct