답안 #867749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867749	2023-10-29T12:14:33 Z	BoopyTheNoob	Tracks in the Snow (BOI13_tracks)	C++14	97.8125 / 100	391 ms	126736 KB

tracks

#include <bits/stdc++.h>
using namespace std;

int main (void) {
    iostream::sync_with_stdio(false);
	cin.tie(0);
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int N, M;
    cin >> N >> M;
    //vector<string> grid(N);
    string grid[4000];
    for (int i = 0; i < N; i++)
        cin >> grid[i];
    //vector<vector<int>> dist(N, vector<int>(M, 0));
    int dist[4000][4000];
    deque<pair<int, int>> bfs;
    bfs.push_back({0, 0});
    dist[0][0] = 1;
    int ans = 1;
    while (!bfs.empty()) {
        int x = bfs.front().first, y = bfs.front().second;
        bfs.pop_front();
        ans = max(ans, dist[x][y]);
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                continue;
            if (dist[nx][ny] != 0 || grid[nx][ny] == '.')
                continue;
            pair<int, int> next = {nx, ny};
            if (grid[x][y] != grid[nx][ny]) {
                dist[nx][ny] = dist[x][y] + 1;
                bfs.push_back(next);
            } else {
                dist[nx][ny] = dist[x][y];
                bfs.push_front(next);
            }
        }
    }
    /*for (auto x: dist) {
        for (auto y: x) {
            cout << y << " ";
        }
        cout << endl;
    }*/
    cout << ans << endl;
    return 0;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	63324 KB	Output is correct
2	Correct	28 ms	63068 KB	Output is correct
3	Correct	29 ms	63068 KB	Output is correct
4	Correct	31 ms	63520 KB	Output is correct
5	Correct	30 ms	63068 KB	Output is correct
6	Correct	29 ms	63004 KB	Output is correct
7	Correct	30 ms	63060 KB	Output is correct
8	Correct	28 ms	63068 KB	Output is correct
9	Correct	29 ms	63060 KB	Output is correct
10	Correct	30 ms	63068 KB	Output is correct
11	Correct	29 ms	63060 KB	Output is correct
12	Correct	30 ms	63056 KB	Output is correct
13	Correct	29 ms	63300 KB	Output is correct
14	Correct	30 ms	63244 KB	Output is correct
15	Correct	34 ms	63216 KB	Output is correct
16	Correct	35 ms	63272 KB	Output is correct
17	Correct	39 ms	63312 KB	Output is correct
18	Correct	32 ms	63580 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	63320 KB	Output is correct
2	Correct	60 ms	65080 KB	Output is correct
3	Correct	147 ms	80720 KB	Output is correct
4	Correct	64 ms	67140 KB	Output is correct
5	Correct	101 ms	72784 KB	Output is correct
6	Correct	388 ms	93980 KB	Output is correct
7	Correct	29 ms	63072 KB	Output is correct
8	Correct	29 ms	63068 KB	Output is correct
9	Correct	30 ms	63248 KB	Output is correct
10	Correct	29 ms	63068 KB	Output is correct
11	Correct	35 ms	63060 KB	Output is correct
12	Correct	29 ms	63056 KB	Output is correct
13	Correct	50 ms	64604 KB	Output is correct
14	Correct	41 ms	64140 KB	Output is correct
15	Correct	36 ms	64088 KB	Output is correct
16	Correct	39 ms	63752 KB	Output is correct
17	Correct	87 ms	67412 KB	Output is correct
18	Correct	61 ms	67152 KB	Output is correct
19	Correct	60 ms	66904 KB	Output is correct
20	Correct	57 ms	66652 KB	Output is correct
21	Correct	100 ms	73148 KB	Output is correct
22	Correct	93 ms	72812 KB	Output is correct
23	Correct	148 ms	71584 KB	Output is correct
24	Correct	93 ms	72784 KB	Output is correct
25	Incorrect	63 ms	80724 KB	Output isn't correct
26	Correct	340 ms	126736 KB	Output is correct
27	Correct	307 ms	99068 KB	Output is correct
28	Correct	391 ms	94112 KB	Output is correct
29	Correct	379 ms	91852 KB	Output is correct
30	Correct	371 ms	97740 KB	Output is correct
31	Correct	302 ms	74692 KB	Output is correct
32	Correct	320 ms	97732 KB	Output is correct