The earth is under an attack of a deadly virus. Luckily, prompt actions
of the Ministry of Health against this emergency successfully confined
the spread of the infection within a square grid of areas. Recently,
public health specialists found an interesting pattern with regard to
the transition of infected areas. At each step in time, every area in
the grid changes its infection state according to infection states of
its directly (horizontally, vertically, and diagonally) adjacent areas.
- An infected area continues to be infected if it has two or three adjacent infected areas.
- An uninfected area becomes infected if it has exactly three adjacent infected areas.
- An area becomes free of the virus, otherwise.
Your mission is to fight against the virus and disinfect all the areas. The Ministry of Health
lets an anti-virus vehicle prototype under your command. The functionality of the vehicle is
summarized as follows.
- At the beginning of each time step, you move the vehicle to one of the eight adjacent
areas. The vehicle is not allowed to move to an infected area (to protect its operators
from the virus). It is not allowed to stay in the same area.
- Following vehicle motion, all the areas, except for the area where the vehicle is in,
change their infection states according to the transition rules described above.
Special functionality of the vehicle protects its area from virus infection even if the area
is adjacent to exactly three infected areas. Unfortunately, this virus-protection capability
of the vehicle does not last. Once the vehicle leaves the area, depending on the infection
states of the adjacent areas, the area can be infected.
The area where the vehicle is in, which is uninfected, has the same effect to its
adjacent areas as an infected area as far as the transition rules are concerned.
The following series of figures illustrate a sample scenario that successfully achieves the
goal.
Initially, your vehicle denoted by @ is found at (1, 5) in a
5 x 5-grid of
areas, and you see some infected areas which are denoted by #'s.
| 1-begin | 1-end | 2-begin | 2-end | 3-begin | 3-end |
| ....@ | ..... | ..... | ..... | .#... | .#... | ..... |
|
##... | ##.@. | ##.@. | ##@.. | #.@.. | #..@. | ...@. |
|
#.... | #.... | ###.. | ###.. | ..... | ..... | ..... |
|
...#. | ...#. | ##### | ##### | #...# | #...# | ..... |
|
##.## | ##.## | ..### | ..### | ....# | ....# | .....
|
Figure 14: A Successful Disinfection Sequence
Firstly, at the beginning of time step 1, you move your vehicle diagonally to the southwest,
that is, to the area (2, 4). Note that this vehicle motion was possible because this area was
not infected at the start of time step 1.
Following this vehicle motion, infection state of each area changes according to the
transition rules. The column ``1-end" of the figure illustrates the result of such changes
at the end of time step 1. Note that the area (3, 3) becomes infected because there were
two adjacent infected areas and the vehicle was also in an adjacent area, three areas in
total.
In time step 2, you move your vehicle to the west and position it at (2, 3).
Then infection states of other areas change. Note that even if your vehicle had exactly
three infected adjacent areas (west, southwest, and south), the area that is being visited
by the vehicle is not infected. The result of such changes at the end of time step
2 is as depicted in ``2-end".
Finally, in time step 3, you move your vehicle to the east. After the change of the
infection states, you see that all the areas have become virus free! This completely
disinfected situation is the goal. In the scenario we have seen, you have successfully
disinfected all the areas in three time steps by commanding the vehicle to move (1)
southwest, (2) west, and (3) east.
Your mission is to find the length of the shortest sequence(s) of vehicle motion commands
that can successfully disinfect all the areas.
The input is a sequence of datasets. The end of the input is indicated by a line
containing a single zero. Each dataset is formatted as follows.
n
a11 a12 ... a1n
a21 a22 ... a2n
...
a1n a2n ... ann
Here, n is the size of the grid. That means that the grid is comprised of
n x n
areas. You may assume
1
n5. The rest of the dataset consists of n lines of n
letters. Each letter aij specifies the state of the area at the beginning: `#'
for infection, `.' for free of virus, and `@' for the initial location of
the vehicle. The only character that can appear in a line is `#', `.',
or `@'. Among
n x n areas, there exists exactly one area which has `@'.
For each dataset, output the minimum number of time steps that is required to disinfect all
the areas. If there exists no motion command sequence that leads to complete disinfection,
output `-1'. The output should not contain any other extra character.
3
...
.@.
...
3
.##
.#.
@##
3
##.
#..
@..
5
....@
##...
#....
...#.
##.##
5
#...#
...#.
#....
...##
..@..
5
#....
.....
.....
.....
..@..
5
#..#.
#.#.#
.#.#.
....#
.#@##
5
..##.
..#..
#....
#....
.#@..
0
0
10
-1
3
2
1
6
4
題目類似於生命遊戲，車子相當於一個感染區域，每個時刻車子會移動到下一個未受感染的區域。
而藉由移動與感染規則，有機會將所有感染區域清除。
所有移動有八個方位。
為了加快內存處理，採用 bitmap 進行壓縮。每個位置的訊息用 2-bit 表示。
而由於圖形最多 5x5, 因此才 50 bits, 最後用一個 long long 塞。
把所有可能進行一次 bfs。
#include <stdio.h>
#include <queue>
#include <map>
using namespace std;
int dx[] = {0,0,1,1,1,-1,-1,-1};
int dy[] = {1,-1,0,1,-1,0,1,-1};
int n;
int check(int x, int y, long long g, long long &ret) {
int cnt = 0, i, j, k, tx, ty;
int e, e2, adj, ve;
long long v;
ret = 0;
v = (x*n+y)*2;
ret |= 2LL<<v;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
v = (i*n+j)*2;
e = (g>>v)&3;//e = g[i][j];
adj = 0;
if(e == 1) {//infected area
for(k = 0; k < 8; k++) {
tx = i+dx[k], ty = j+dy[k];
if(tx < 0 || ty < 0 || tx >= n || ty >= n) continue;
v = (tx*n+ty)*2;
e2 = (g>>v)&3;//e2 = g[tx][ty]
if(e2 == 1 || (tx == x && ty == y)) {
adj++;
if(adj > 3) k = 8;
}
}
if(adj == 2 || adj == 3)
ve = 1;//last become infected area
else
ve = 0;
} else {
if(i == x && j == y) ve = 2;
else {
for(k = 0; k < 8; k++) {
tx = i+dx[k], ty = j+dy[k];
if(tx < 0 || ty < 0 || tx >= n || ty >= n) continue;
v = (tx*n+ty)*2;
e2 = (g>>v)&3;//e2 = g[tx][ty]
if(e2 == 1 || (tx == x && ty == y)) {
adj++;
if(adj > 3) k = 8;
}
}
if(adj == 3)
ve = 1;
else
ve = 0;
}
}
v = (i*n+j)*2;
ret |= ((long long)ve)<<v;
cnt += (ve == 1);
}
}
return cnt == 0;
}
void bfs(long long st) {
queue<long long> Q;
map<long long, int> R;
long long tn, ttn;
int i, j, v, x, y, tx, ty;
int s, ss;
int flag;
R[st] = 1;
Q.push(st);
while(!Q.empty()) {
tn = Q.front(), Q.pop();
x = -1;
for(i = 0; i < n; i++) {//find '@'
for(j = 0; j < n; j++) {
v = (i*n+j)*2;
if(((tn>>v)&3) == 2)
x = i, y = j, i = n, j = n;
}
}
int s = R[tn];
for(i = 0; i < 8; i++) {
tx = x+dx[i], ty = y+dy[i];
if(tx < 0 || ty < 0 || tx >= n || ty >= n)
continue;
v = (tx*n+ty)*2;
if(((tn>>v)&3) == 0) {//if g[tx][ty] = '.'
flag = check(tx, ty, tn, ttn);
if(flag == 1) {//solution
printf("%d\n", s);
return;
}
int &ss = R[ttn];
if(ss == 0) {
ss = s+1;
Q.push(ttn);
}
}
}
if(flag == 1)
break;
}
puts("-1");
}
int main() {
int i, j;
char g[10][10];
while(scanf("%d", &n) == 1 && n) {
for(i = 0; i < n; i++)
scanf("%s", &g[i]);
long long val = 0;
int cnt = 0, v;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
v = (i*n+j)*2;
if(g[i][j] == '.')
val |= 0LL<<v;
else if(g[i][j] == '#')
val |= 1LL<<v, cnt++;
else
val |= 2LL<<v;
}
}
if(cnt == 0)
puts("0");
else
bfs(val);
}
return 0;
}
文章定位：
