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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
#include"osalib.h"
using namespace std;
# ifdef DEB
# define debug(...) fprintf(stderr, __VA_ARGS__)
# else
# define debug(...)
#endif
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define LD long double
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define pb pop_back
#define VI vector<int>
#define VPI vector<PII>
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define FORD(i,a,b) for(int i = (a); i >= (b); i--)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define ALL(x) (x).begin(), (x).end()
#define siz(V) ((int)V.size())
#define LL long long
static const int M = 1024;

static int B[M][M], vis[M][M];
static int nn, mm, os, tim;
static PII start;
static int mx[] = {1, -1, 0, 0}, my[] = {0, 0, 1, -1};

void NowaWyspa(int n, int m, char **board)
{
  nn = n;
  mm = m;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      if (board[i][j] == '.')
      {
        B[i + 1][j + 1] = 1;
      }
      if (board[i][j] == 'K')
      {
        B[i + 1][j + 1] = 2;
        start = MP(i + 1, j + 1);
        os++;
      }
    }
  }
}

static int DFS(PII x)
{
  vis[x.F][x.S] = tim;
  int s = (B[x.F][x.S] == 2);
  for (int i = 0; i < 4; i++)
  {
    PII xx = MP(x.F + mx[i], x.S + my[i]);
    if (vis[xx.F][xx.S] != tim && B[xx.F][xx.S] != 0)
    {
      s += DFS(xx);
    }
  }
  return s;
}

int NowaWarownia(int r, int c)
{
  tim++;
  B[r][c] = 0;
  if (DFS(start) != os)
  {
    B[r][c] = 1;
    return 0;
  }
  return 1;
}

void PrzeniesOsade(int r1, int c1, int r2, int c2)
{
  if (start == MP(r1, c1))
  {
    start = MP(r2, c2);
  }
  B[r2][c2] = 2;
  B[r1][c1] = 1;
}