답안 #584541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584541	2022-06-27T14:20:02 Z	Andrei_Calota	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1072 ms	130968 KB

tracks

#include <bits/stdc++.h>

using namespace std;
const int SIZE_OF = 4e3;
const char VISITED = '*';
const int VISUAL = 4;

int n, m;
int dl[] = { -1, 0,  1,  0 };
int dc[] = {  0, 1,  0, -1 };
char input[2 + SIZE_OF][2 + SIZE_OF];
int depth[1 + SIZE_OF][1 + SIZE_OF];

void solve ( pair<int, int> start ) {
   deque<pair<int, int>> bfs_q;
   bfs_q.push_front ( start );
   depth[start.first][start.second] = 1;

   int answer = 1;
   while ( !bfs_q.empty () ) {
      start = bfs_q.front (); bfs_q.pop_front ();
      answer = max ( answer, depth[start.first][start.second] );

      int line = start.first, column = start.second;
      for ( int dir = 0; dir < VISUAL; dir ++ ) {
         int next_line = line + dl[dir];
         int next_col = column + dc[dir];
         if ( depth[next_line][next_col] == 0 && input[next_line][next_col] != '.' && input[next_line][next_col] != VISITED ) {
           if ( input[line][column] == input[next_line][next_col] ) {
             depth[next_line][next_col] = depth[line][column];
             bfs_q.push_front ( {next_line, next_col} );
           }
           else {
             depth[next_line][next_col] = depth[line][column] + 1;
             bfs_q.push_back ( {next_line, next_col} );
           }
         }
      }
   }
   cout << answer;
}
int main()
{
   cin >> n >> m; cin.get ();
   for ( int line = 1; line <= n; line ++ ) {
      for ( int column = 1; column <= m; column ++ )
         input[line][column] = cin.get ();
      cin.get ();
   }
   for ( int line = 0; line < n + 2; line ++ )
      input[line][0] = input[line][m + 1] = VISITED;
   for ( int column = 0; column < m + 2; column ++ )
      input[0][column] = input[n + 1][column] = VISITED;
   solve ( {1, 1} );
    return 0;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	5316 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	688 KB	Output is correct
4	Correct	12 ms	5132 KB	Output is correct
5	Correct	6 ms	2852 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	692 KB	Output is correct
8	Correct	1 ms	828 KB	Output is correct
9	Correct	1 ms	1108 KB	Output is correct
10	Correct	5 ms	2388 KB	Output is correct
11	Correct	4 ms	2132 KB	Output is correct
12	Correct	8 ms	3028 KB	Output is correct
13	Correct	6 ms	2900 KB	Output is correct
14	Correct	6 ms	2900 KB	Output is correct
15	Correct	18 ms	5196 KB	Output is correct
16	Correct	22 ms	5400 KB	Output is correct
17	Correct	18 ms	5204 KB	Output is correct
18	Correct	13 ms	5204 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	30804 KB	Output is correct
2	Correct	96 ms	15012 KB	Output is correct
3	Correct	828 ms	73352 KB	Output is correct
4	Correct	204 ms	32680 KB	Output is correct
5	Correct	442 ms	53244 KB	Output is correct
6	Correct	1046 ms	108764 KB	Output is correct
7	Correct	16 ms	32132 KB	Output is correct
8	Correct	17 ms	30804 KB	Output is correct
9	Correct	4 ms	572 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	18 ms	31552 KB	Output is correct
12	Correct	2 ms	1548 KB	Output is correct
13	Correct	96 ms	15008 KB	Output is correct
14	Correct	59 ms	10424 KB	Output is correct
15	Correct	60 ms	13092 KB	Output is correct
16	Correct	43 ms	5584 KB	Output is correct
17	Correct	238 ms	28816 KB	Output is correct
18	Correct	217 ms	35728 KB	Output is correct
19	Correct	214 ms	32672 KB	Output is correct
20	Correct	173 ms	25548 KB	Output is correct
21	Correct	457 ms	52664 KB	Output is correct
22	Correct	457 ms	53312 KB	Output is correct
23	Correct	449 ms	43856 KB	Output is correct
24	Correct	460 ms	49740 KB	Output is correct
25	Correct	872 ms	94164 KB	Output is correct
26	Correct	738 ms	130968 KB	Output is correct
27	Correct	930 ms	123516 KB	Output is correct
28	Correct	1072 ms	108924 KB	Output is correct
29	Correct	1048 ms	104884 KB	Output is correct
30	Correct	983 ms	112304 KB	Output is correct
31	Correct	747 ms	73400 KB	Output is correct
32	Correct	920 ms	113980 KB	Output is correct