SameGame Simulation

The one-player game of SameGame is played on an M row by N column rectangular grid. In each cell of the grid is placed a positive integer in the range 0 through 9. The goal of the game is to remove all the integers from the grid. The player attempts this by repeatedly selecting a cell for removal. Each time a cell is selected for removal, all the cells in the connected region (defined below) containing the same integer found in selected cell are removed, and all cells above those that were removed ``drop down" (toward the bottom of the grid). When all the cells in a column have been removed, then columns to the right of the removed column slide to the left. The game is over when all cells are removed (a win), or when no more cells can be removed.

A connected region consists of all cells that can be reached by moving horizontally (left or right) and/or vertically (up or down) from any cell in the region, subject to the restriction that all cells in the connected region must contain the same value.

Cells will be numbered starting with the lower left corner of the grid; this is cell (1,1). The cell above it is cell (2,1), and the cell to its right is cell (1,2).

The cells at (1,1), (2,5), (3,1), (3,2) and (3,3) may not be successfully selected for removal, since they aren�'t parts of connected regions (i.e., regions that contain at least two connected cells with the same value). The cell at (2,1) is part of the connected region also containing the cells at (2,2) and (1,2). Likewise, the connected region containing the cell at (1,5) also contains the cells at (1,4) and (2,4), but not the cell at (3,3). Starting with the original grid shown above, the following selections will result in a win:

•   
  1 3 5     
  2 2 3 5 1 
  1 2 3 5 5

•     5     
  1   3 5 1 
  1 3 3 5 5

• 1   5 1   
  1 5 5 5

• 1         
  1 1

Finally, in step 5, selecting cell (1,1), (1,2) or (2,1) will remove the remaining integers from the grid.

In the input for this problem your program will be presented with a sequence of grids, each having no more than 10 rows and 40 columns. For each grid there will also be given a sequence of cell removal selections. Apply these selections, in order, to each grid, ignoring those that are not permitted (e.g. they select non-existant cells, or they select regions with fewer than two cells). Then display the resulting grid or, if appropriate, the message "Game Won".

Input

The input will consist entirely of non-negative integers without regard to line structure. Each grid and sequence of removal selections will begin with values for M and N. If either of these values is zero, then the input is terminated.

Following M and N will appear the integers for the grid, in row major order. That is, the values are given in order for cells (1,1), (1,2), ..., (1,N), (2,1), ..., (M,N). Following the grid data will appear pairs of integers, each pair indicating the row and column of a grid cell selected for removal. The end of this sequence will be marked by a pair of zeroes.

If a game is won, your program must skip any remaining pairs of integers (if any) through and including the pair of zeroes to reach the data for the next grid in the input.

Output

As noted above, the output for each grid in the input data should be either the grid that remains after considering all selections, or the message "Game Won". Precede the output for each grid by its sequence in the input; the first grid is numbered 1.

Look at the samples below for the exact format.

Sample Input

3 5
1 2 3 5 5
2 2 3 5 1
1 3 5 2 2
3 5
2 2
1 2
1 2
1 1
0 0

3 5
1 2 3 5 5
2 2 3 5 1
1 3 5 2 2
2 2    1 2   1 4   1 2   
99 99 0 0

4 3
1 4 4
4 4 2
1 2 3
3 1 3
1 2 1 1 1 3 1 1 0 0
0 0

Sample Output

Grid 1.
    Game Won

Grid 2.
              
    1   2     
    1 2 1     

Grid 3.
    Game Won

---

題目描述：

一個消去遊戲，不過這裡模擬即可，點了不見得會有消去效果。
必須要有 2 個(含)以上，才可執行消去動作。

題目輸入的圖是倒過來的，每消一次，先執行下落動作，再執行靠左并的動作。

題目解法：

模擬，這裡使用 special judge 只有檢察最後一行的問題而已。

#include <stdio.h>
int g[105][105], n, m;
int booomTest(int x, int y) {
    if(x <= 0 || y <= 0 || x > n || y > m)
        return 0;
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    int i, tx, ty;
    if(g[x][y] <= 0)    return 0;
    for(i = 0; i < 4; i++) {
        tx = x+dx[i], ty = y+dy[i];
        if(tx <= 0 || ty <= 0 || tx > n || ty > m)
            continue;
        if(g[tx][ty] == g[x][y])
            return 1;
    }
    return 0;
}
void booom(int x, int y, int v) {
    if(x <= 0 || y <= 0 || x > n || y > m)
        return;
    if(g[x][y] != v)    return;
    g[x][y] = 0;
    booom(x+1, y, v);
    booom(x-1, y, v);
    booom(x, y+1, v);
    booom(x, y-1, v);
}
void dropDown() {
    int i, j, k;
    for(i = 1; i <= m; i++) {
        for(j = 1, k = 1; j <= n; j++) {
            if(g[j][i])
                g[k++][i] = g[j][i];
        }
        while(k <= n)   g[k++][i] = 0;
    }
}
void slideLeft() {
    int i, j, k;
    for(i = 1, k = 1; i <= m; i++) {
        for(j = 1; j <= n; j++)
            if(g[j][i]) break;
        if(j != n+1) {
            for(j = 1; j <= n; j++)
                g[j][k] = g[j][i];
            k++;
        }
    }
    while(k <= m) {
        for(j = 1; j <= n; j++)
            g[j][k] = 0;
        k++;
    }
}
int main() {
    int i, j, x, y;
    int cases = 0;
    while(scanf("%d %d", &n, &m) == 2 && n) {
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= m; j++) {
                scanf("%d", &g[i][j]);
                g[i][j]++;
            }
        }
        while(scanf("%d %d", &x, &y) == 2) {
            if(x == 0 && y == 0)
                break;
            if(booomTest(x, y) == 0)
                continue;
            booom(x, y, g[x][y]);
            dropDown();
            slideLeft();
        }
        if(cases)   puts("");
        printf("Grid %d.\n", ++cases);
        int win = 1;
        for(i = 1; i <= n; i++)
            for(j = 1; j <= m; j++)
                win &= g[i][j] == 0;
        if(win) {
            puts("    Game Won");
        } else {
            for(i = n; i >= 1; i--) {
                printf("   ");
                for(j = 1; j <= m; j++) {
                    printf(" ");
                    if(g[i][j]) printf("%d", g[i][j]-1);
                    else        printf(" ");
                }
                puts("");
            }
        }
    }
    return 0;
}