답안 #793312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
793312	2023-07-25T17:44:54 Z	olisoe	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	526 ms	136996 KB

tracks

#include "iostream"
#include "vector"
#include "algorithm"
#include "queue"
#include "set"
#include "unordered_set"
#include "stack"
#include "map"
#include "limits.h"
#include "cstdio"
#include "math.h"
#include <numeric>
using namespace std;

int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
int n,m,ans = 1;
vector<vector<int>> depth(4000,vector<int>(4000));
vector<string> snow(4000);
bool inside(int x,int y)
{
    return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for(int i = 0; i<n; i++)
        cin>>snow[i];
    deque<pair<int,int>>q;
    q.push_back({0,0});
    depth[0][0]=1;
    while (q.size()) {
        pair<int, int> c = q.front();
        q.pop_front();
        ans = max(ans, depth[c.first][c.second]);

        for (int i = 0; i < 4; i++) {
            int x = c.first + dx[i], y = c.second + dy[i];
            if (inside(x, y) && depth[x][y] == 0) {
                if (snow[x][y] == snow[c.first][c.second]) {
                    depth[x][y] = depth[c.first][c.second];
                    q.push_front({x, y});
                } else {
                    depth[x][y] = depth[c.first][c.second] + 1;
                    q.push_back({x, y});
                }
            }
        }
    }

    cout << ans;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	63692 KB	Output is correct
2	Correct	27 ms	63128 KB	Output is correct
3	Correct	28 ms	63212 KB	Output is correct
4	Correct	37 ms	63624 KB	Output is correct
5	Correct	36 ms	63288 KB	Output is correct
6	Correct	34 ms	63180 KB	Output is correct
7	Correct	27 ms	63140 KB	Output is correct
8	Correct	27 ms	63188 KB	Output is correct
9	Correct	28 ms	63216 KB	Output is correct
10	Correct	27 ms	63244 KB	Output is correct
11	Correct	28 ms	63308 KB	Output is correct
12	Correct	30 ms	63320 KB	Output is correct
13	Correct	28 ms	63312 KB	Output is correct
14	Correct	29 ms	63380 KB	Output is correct
15	Correct	33 ms	63616 KB	Output is correct
16	Correct	35 ms	63644 KB	Output is correct
17	Correct	41 ms	63604 KB	Output is correct
18	Correct	37 ms	63668 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	63156 KB	Output is correct
2	Correct	53 ms	66300 KB	Output is correct
3	Correct	185 ms	91104 KB	Output is correct
4	Correct	67 ms	70760 KB	Output is correct
5	Correct	128 ms	81736 KB	Output is correct
6	Correct	522 ms	104788 KB	Output is correct
7	Correct	29 ms	63244 KB	Output is correct
8	Correct	29 ms	63220 KB	Output is correct
9	Correct	29 ms	63292 KB	Output is correct
10	Correct	28 ms	63196 KB	Output is correct
11	Correct	30 ms	63268 KB	Output is correct
12	Correct	28 ms	63228 KB	Output is correct
13	Correct	53 ms	66396 KB	Output is correct
14	Correct	44 ms	64972 KB	Output is correct
15	Correct	40 ms	65228 KB	Output is correct
16	Correct	41 ms	64424 KB	Output is correct
17	Correct	93 ms	71372 KB	Output is correct
18	Correct	95 ms	71332 KB	Output is correct
19	Correct	68 ms	70820 KB	Output is correct
20	Correct	59 ms	70220 KB	Output is correct
21	Correct	127 ms	82368 KB	Output is correct
22	Correct	131 ms	81736 KB	Output is correct
23	Correct	163 ms	79184 KB	Output is correct
24	Correct	106 ms	81752 KB	Output is correct
25	Correct	377 ms	91128 KB	Output is correct
26	Correct	280 ms	136996 KB	Output is correct
27	Correct	380 ms	117716 KB	Output is correct
28	Correct	526 ms	104700 KB	Output is correct
29	Correct	474 ms	103084 KB	Output is correct
30	Correct	441 ms	108660 KB	Output is correct
31	Correct	412 ms	84740 KB	Output is correct
32	Correct	316 ms	106440 KB	Output is correct