Submission #36527

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
36527	2017-12-10 08:04:17	cheater2k	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1303 ms	448676 KiB

tracks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = 4005;
const int dx[] = {0, 0, -1, +1};
const int dy[] = {-1, +1, 0, 0};
int r, c;
string a[N];
bool vis[N][N];
int ans;
void bfs(queue< pair<int,int> > &q1, queue< pair<int,int> > &q2) {
  if (q1.empty()) return;
  ++ans;
  while(!q1.empty()) {
    int x = q1.front().first, y = q1.front().second; q1.pop();
    for (int dir = 0; dir < 4; ++dir) {
      int nx = x + dx[dir];
      int ny = y + dy[dir];
      if (nx < 0 || nx >= r || ny < 0 || ny >= c || a[nx][ny] == '.' || vis[nx][ny]) continue;
      vis[nx][ny] = true;
      if (a[nx][ny] != a[x][y]) q2.push(make_pair(nx, ny));
      else q1.push(make_pair(nx, ny));
    }
  }
  bfs(q2, q1);
}
int main() {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70