답안 #421256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421256	2021-06-08T23:28:37 Z	pavanscoding	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	789 ms	130744 KB

tracks

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

int dx[4]={0,0,1,-1}, dy[4]={1,-1,0,0};
int n,m,depth[4000][4000], ans=1;
string grid[4000];

bool check(int x, int y){
    return (x>-1&&x<n&&y>-1&&y<m&&grid[x][y]!='.');
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0;i<n;i++)
        cin >> grid[i];
    deque<pair<int,int>> q;
    q.push_back({0,0});
    depth[0][0]=1;

    while(!q.empty()){
        pair<int,int> t=q.front();
        q.pop_front();
        ans=max(ans,depth[t.first][t.second]);

        for(int i=0;i<4;i++){
            int x=t.first+dx[i], y=t.second+dy[i];
            if(check(x,y)&&depth[x][y]==0){
                if(grid[x][y]==grid[t.first][t.second]){    
                    depth[x][y]=depth[t.first][t.second];
                    q.push_front({x,y});
                }
                else{
                    depth[x][y]=depth[t.first][t.second]+1;
                    q.push_back({x,y});
                }
            }
        }
    }
    cout << ans << "\n";
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	3788 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	568 KB	Output is correct
4	Correct	8 ms	3396 KB	Output is correct
5	Correct	3 ms	1988 KB	Output is correct
6	Correct	1 ms	460 KB	Output is correct
7	Correct	1 ms	588 KB	Output is correct
8	Correct	1 ms	716 KB	Output is correct
9	Correct	1 ms	832 KB	Output is correct
10	Correct	3 ms	1612 KB	Output is correct
11	Correct	3 ms	1484 KB	Output is correct
12	Correct	5 ms	2124 KB	Output is correct
13	Correct	3 ms	1996 KB	Output is correct
14	Correct	3 ms	1996 KB	Output is correct
15	Correct	10 ms	3656 KB	Output is correct
16	Correct	13 ms	3868 KB	Output is correct
17	Correct	9 ms	3676 KB	Output is correct
18	Correct	8 ms	3428 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	15820 KB	Output is correct
2	Correct	38 ms	11784 KB	Output is correct
3	Correct	189 ms	75268 KB	Output is correct
4	Correct	61 ms	29340 KB	Output is correct
5	Correct	144 ms	51652 KB	Output is correct
6	Correct	647 ms	109452 KB	Output is correct
7	Correct	11 ms	16588 KB	Output is correct
8	Correct	10 ms	15888 KB	Output is correct
9	Correct	2 ms	716 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	11 ms	16232 KB	Output is correct
12	Correct	1 ms	1100 KB	Output is correct
13	Correct	38 ms	11844 KB	Output is correct
14	Correct	22 ms	7860 KB	Output is correct
15	Correct	18 ms	10316 KB	Output is correct
16	Correct	21 ms	4908 KB	Output is correct
17	Correct	99 ms	25260 KB	Output is correct
18	Correct	75 ms	32120 KB	Output is correct
19	Correct	62 ms	29596 KB	Output is correct
20	Correct	48 ms	22420 KB	Output is correct
21	Correct	118 ms	50484 KB	Output is correct
22	Correct	151 ms	51652 KB	Output is correct
23	Correct	191 ms	42308 KB	Output is correct
24	Correct	125 ms	47592 KB	Output is correct
25	Correct	430 ms	96272 KB	Output is correct
26	Correct	789 ms	130744 KB	Output is correct
27	Correct	597 ms	114504 KB	Output is correct
28	Correct	635 ms	109520 KB	Output is correct
29	Correct	625 ms	107196 KB	Output is correct
30	Correct	658 ms	111760 KB	Output is correct
31	Correct	497 ms	72072 KB	Output is correct
32	Correct	693 ms	112392 KB	Output is correct