about summary refs log tree commit diff
path: root/others/other/vdd.cpp
blob: 5743bbb2b3b69561b0d4fdecc3d8b3a0aede2886 (plain) (blame)
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

#define POINT(x, y) (((x) << 7) + (y))
#define ENC(s, x, y) (((s) << 14) + ((x) << 7) + (y))

void
explore(short x, short y, short n, short a[102][102], short* p[102][102])
{
  short i, j;
  short* area = p[x][y];
  queue<short> q;
  q.push(POINT(x, y));

  while (!q.empty())
    {
      i = q.front();
      q.pop();
      j = i & 127;
      i >>= 7;

      if (i > 1 && a[i - 1][j] && !p[i - 1][j])
        {
          (*area)++;
          p[i - 1][j] = area;
          q.push(POINT(i - 1, j));
        }
      if (i < n && a[i + 1][j] && !p[i + 1][j])
        {
          (*area)++;
          p[i + 1][j] = area;
          q.push(POINT(i + 1, j));
        }
      if (j > 1 && a[i][j - 1] && !p[i][j - 1])
        {
          (*area)++;
          p[i][j - 1] = area;
          q.push(POINT(i, j - 1));
        }
      if (j < n && a[i][j + 1] && !p[i][j + 1])
        {
          (*area)++;
          p[i][j + 1] = area;
          q.push(POINT(i, j + 1));
        }
    }
}

int
main()
{
  short n, x, y, i, j, a[102][102] = {};
  ifstream infile;
  infile.open("VDD.INP");
  infile >> n >> x >> y;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      infile >> a[i][j];
  infile.close();

  short* p[102][102] = {};
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      if (a[i][j] && !p[i][j])
        {
          p[i][j] = (short*) malloc(sizeof(short));
          *p[i][j] = 1;
          explore(i, j, n, a, p);
        }

  priority_queue<long, vector<long>, greater<long>> heap;
  bool visited[102][102] = {};
  queue<short> q;
  visited[x][y] = true;
  q.push(POINT(x, y));
  while (!q.empty())
    {
      i = q.front();
      q.pop();
      j = i & 127;
      i >>= 7;
      if (!(a[i + 1][j] && a[i][j + 1] && a[i - 1][j] && a[i][j - 1]))
        heap.push(POINT(i, j));

      if (i > 1 && !visited[i - 1][j] && a[i - 1][j])
        {
          q.push(POINT(i - 1, j));
          visited[i - 1][j] = true;
        }
      if (i < n && !visited[i + 1][j] && a[i + 1][j])
        {
          q.push(POINT(i + 1, j));
          visited[i + 1][j] = true;
        }
      if (j > 1 && !visited[i][j - 1] && a[i][j - 1])
        {
          q.push(POINT(i, j - 1));
          visited[i][j - 1] = true;
        }
      if (j < n && !visited[i][j + 1] && a[i][j + 1])
        {
          q.push(POINT(i, j + 1));
          visited[i][j + 1] = true;
        }
    }

  short* current = p[x][y], s = 12345;
  long tmp;
  while (!heap.empty())
    {
      tmp = heap.top();
      heap.pop();
      i = tmp >> 7 & 127;
      j = tmp & 127;
      tmp >>= 14;
      if (tmp > s)
        break;
      if (p[i][j] && p[i][j] != current)
        if (*p[i][j] <= *current)
          continue;
        else
          {
            s = tmp;
            *current = *p[i][j];
          }

      tmp++;
      if (i && !visited[i - 1][j])
        {
          heap.push(ENC(tmp, i - 1, j));
          visited[i - 1][j] = true;
        }
      if (i < n + 1 && !visited[i + 1][j])
        {
          heap.push(ENC(tmp, i + 1, j));
          visited[i + 1][j] = true;
        }
      if (j && !visited[i][j - 1])
        {
          heap.push(ENC(tmp, i, j - 1));
          visited[i][j - 1] = true;
        }
      if (j < n + 1 && !visited[i][j + 1])
        {
          heap.push(ENC(tmp, i, j + 1));
          visited[i][j + 1] = true;
        }
    }

  ofstream outfile;
  outfile.open("VDD.OUT");
  outfile << (s == 12345 ? 0 : s - 1) << endl;
  outfile.close();

  return 0;
}