Submission #584541

#	Time	Username	Problem	Language	Result	Execution time	Memory
584541		Andrei_Calota	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1072 ms	130968 KiB

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 / 30
• Subtask 2: 70 / 70