URAL 1122. Game
1. 题目
http://acm.timus.ru/problem.aspx?space=1&num=1122
1122. Game
Time limit: 1.0 second
Memory limit: 64 MB
At SKB Kontur we have to work much. So there is no sin in taking a rest and playing from time to time. Consider for example the following famous one-player game.
We have a 4×4 field. There are chips with one side painted white and another side painted black on the field. Some of the chips are with their white side up and the others are with their white side down at the moment. Each move consists in turning over a chip together with all the chips that are adjacent to it vertically and horizontally (i.e. 5 chips altogether). The aim is to come to the position in which all the chips are with the same side up.
Naturally, one is easily bored with this game because interesting and unexpected positions become fewer as time goes on. That is why a modified version of the game is now more popular at SKB Kontur. In this version a move consists in turning over a fixed combination of chips within a 3×3 square. For example, a move may consist in turning over all the diagonal neighbors of a chosen chip.
The combination of chips is chosen arbitrarily; it may be assigned in the form of a 3×3 field in which the central cell corresponds to the cell at which a move as made. For example, in picture at the left the upper combination corresponds to a standard game and the lower combination is for the game described in the previous paragraph. Note that a combination can be asymmetrical. Each move is made at one of the cells of the playing field (i.e. the central cell of the 3×3 move-defining square is selected among the field’s cells). Prescriptions to turn over chips at cells which are outside the 4×4 field are ignored.In this game it would be nice to know if it is possible to reach a position in which all the chips are with the same side up and if it’s possible to do this then in how many moves. You are to write a program which answers these questions.Input
The first four lines describe the initial arrangement of chips. A symbol “W” stands for a chip which lies with its white side up and a symbol “B” stands for a chip which lies with its black side up. The next three lines describe a move: the chips that are to be turned over are shown by “1” and others are shown by “0”.Output
If it is impossible to reach the aim of the game you should output the word “Impossible”, otherwise you should output the minimal number of moves necessary to come to the final position.Sample
input output
Problem Source: USU Open Collegiate Programming Contest October’2001 Junior Session
2. 思路
给出一个有4*4个格子的棋盘，每个格子放有一枚棋子，棋子一面是黑色，一面是白色，初始状态随机。给出一个3*3的矩阵，每次操作可以将矩阵放置在棋盘的任意位置（矩阵中心不能超出棋盘范围），对于棋盘上被矩阵覆盖的格子，如果矩阵的值为1，则翻转格子中的旗子。求是否能够将所有棋子都翻转为相同颜色。
BFS。由于棋盘只有16个格子，可以将棋盘状态压缩至16 bit来表示，根据矩阵位置，得到对应操作的掩码，与棋盘状态进行与运算，得到翻转后的棋盘状态。由此可以大大降低内存占用。
3. 代码
inputPattern()将4*4的棋盘压缩至16 bit，inputMove()根据输入的3*3操作矩阵，计算得到所有16种可能对棋盘进行的操作，同样使用16 bit表示。在BFS时，将当前棋盘状态curr与所有16中操作move[]进行与运算，得到所有翻转后的棋盘状态。
#include <cstdio>
#define MAX_PATTERN_NUM 65536
#define FLAG -1
void solveUral1122_Game();
int inputPattern(int width);
void inputMove(int move[]);
int main() {
// freopen("test.txt", "r", stdin);
solveUral1122_Game();
return 0;
}
int queue[MAX_PATTERN_NUM];
bool visited[MAX_PATTERN_NUM];
void solveUral1122_Game() {
int initPattern = inputPattern(4);
int move[16];
inputMove(move);
int front = 0, rear = 0;
queue[rear++] = initPattern;
visited[initPattern] = true;
queue[rear++] = FLAG;
int stepNum = 0;
bool found = false;
while (front != rear) {
int curr = queue[front++];
if (curr == FLAG) {
if (front != rear) {
++stepNum;
queue[rear++] = FLAG;
continue;
}
} else if (curr == 65535 || curr == 0) {
found = true;
break;
}
for (int i = 0; i < 16; ++i) {
int next = curr ^ move[i];
if (!visited[next]) {
queue[rear++] = next;
// printf("%d\n", rear);
visited[next] = true;
}
}
}
if (found) {
printf("%d\n", stepNum);
} else {
printf("Impossible\n");
}
}
int inputPattern(int width) {
char ch;
int result = 0;
for (int i = 0, cnt = 0; i < width; ++i) {
for (int j = 0; j < width; ++j, ++cnt) {
scanf("%c", &ch);
if (ch == 'W')
result += 1 << cnt;
}
getchar();
}
return result;
}
void inputMove(int move[]) {
char initMove[9];
int shift[6][6] = {
{ -1, -1, -1, -1, -1, -1 },
{ -1, 0, 1, 2, 3, -1 },
{ -1, 4, 5, 6, 7, -1 },
{ -1, 8, 9, 10, 11, -1 },
{ -1, 12, 13, 14, 15, -1 },
{ -1, -1, -1, -1, -1, -1 } };
int pos[9][2] = {
{ -1, -1 }, { -1, 0 }, { -1, 1 },
{ 0, -1 }, { 0, 0 }, { 0, 1 },
{ 1, -1 }, { 1, 0 }, { 1, 1 } };
for (int i = 0; i < 9;) {
scanf("%c", &initMove[i]);
if (initMove[i] != '\n')
++i;
}
for (int i = 1, cnt = 0; i <= 4; ++i) {
for (int j = 1; j <= 4; ++j, ++cnt) {
move[cnt] = 0;
for (int k = 0; k < 9; ++k) {
int row = i + pos[k][0], col = j + pos[k][1];
if (shift[row][col] != -1 && initMove[k] == '1') {
move[cnt] += 1 << shift[row][col];
}
}
}
}
}