T3 题解 - 四维网络

Exam02

四维网络

题目描述

这是一个简化版的网络游戏：在一个$N \times N$方块构成的棋盘中，每个方块均涂上红、黄、蓝、绿（记为$1、2、3、4$）中的一种颜色，游戏者可以在最底行任意找一个方块，用鼠标双击这个方块，于是该方块及与之相邻（即在上、下、左、右四个方向上有公共边）的所有的与该方块同色方块均被消掉，而因下方失去支持的方块将会自由落下填补空位。下图左边给出一个$4 \times 4$的棋盘样例，当游戏者双击最底层左边第二个方块后，将会形成右边的布局。
你的任务是编写一个四维网络模拟程序，对于给定的一个初始棋盘，计算游戏者双击最底层某个方块后棋盘的布局将会如何。

输入格式

第一行有两个正整数$N$和$M$（$1 \leq M \leq N \leq 100$），其中$N$表示棋盘的规模，而$M$则表示游戏者将双击最底层从左边数起的第$M$个方块。 接下来的$N$行每行有$N$个$1$至$4$的整数组成，表示一个初始的棋盘，同一行相邻两个数之间用一个空格隔开。

输出格式

有$N$行，每行用$N$个数给出游戏结束后棋盘的布局，没有方块的格子用$0$表示，同一行相邻两个数之间也用一个空格分开。

输入样例

输入样例1

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

输入样例2

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

输出样例

输出样例1

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

输出样例2

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

数据范围

对于$30\%$: $1 \leq n \leq 10$
对于$100\%$: $1 \leq n \leq 100$

题解

直接爆搜，注意如何处理重力。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
int n, m, color, a[N][N];
bool vis[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void dfs (int x, int y) {
    if (x < 1 || x > n || y < 1 || y > n) {//超出地图 
        return;
    }
    if (vis[x][y]) {//判断访问过没有 
        return;
    }
    if (a[x][y] != color) {//判断是否同色 
        return;
    }
    vis[x][y] = 1;
    a[x][y] = 0;
    for (int i = 0; i < 4; i++) {//递归搜索 
        int tx = x + dx[i];
        int ty = y + dy[i];
        dfs (tx, ty);
    }
}
int main() {
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf ("%d", &a[i][j]);
        }
    }
    color = a[n][m];
    dfs (n, m);
    for (int k = 1; k <= n; k++) {//多遍历一次，以防有没有遍历到的 
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i + 1][j] == 0) {
                    swap (a[i + 1][j], a[i][j]);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf ("%d ", a[i][j]);
        }
        printf ("\n");
    }
    return 0;
}