P7187 [CRCI2008-2009] RELJEF 题解

· · 题解

稍显幼稚的小游戏轻松快乐简单小模拟，考察基本广搜 / 深搜判连通块。

题意

每次打破一个方格上的 矿物，然后使单独的“腾空”连通块一直下落，直至与其他连通块相接 / 落至地面。请模拟此操作，矩阵大小 r\times c，1\leqslant r,c\leqslant100。

分析

这有什么好分析的？

唯一一点点问题在于，题中遵循真实物理定律的“下落”。

  1. 确定下落的是哪个块

由于 数据范围与约定 中 “保证在任何时间点都不会有两个或两个以上的碎块群同时落下”，我们可以在被破坏的方格四周轻松找出两个连通块，每个都执行一次下落操作即可。

  1. 下落的实现

简单粗暴地，对于每个连通块中的点，往下依次找，直到碰到地面 / 其他连通块，最后整体下移。

代码

#include<stdio.h>
#include<queue>
using namespace std;
const int maxn = 100;
int r, c, n, cnt, vis[maxn + 5][maxn + 5], dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
char mp[maxn + 5][maxn + 5];
bool isstone(int x, int y) {return x <= r && x && y <= c && y && mp[x][y] == 'x';}
struct node {int x, y;};
void bfs(int sx, int sy, int tag)//对点 (sx,sy) 所在连通块打上 tag 的标记
{
    queue<node> q;
    q.push({sx, sy});
    vis[sx][sy] = tag;
    while(!q.empty())
    {
        node t = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            int nx = t.x + dx[i], ny = t.y + dy[i];
            if(isstone(nx, ny) && !vis[nx][ny]) vis[nx][ny] = tag, q.push({nx, ny});
        }
    }
}
void calc()//重新计算每个点所属连通块
{
    for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) vis[i][j] = 0;
    cnt = 0;
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            if(isstone(i, j) && !vis[i][j]) bfs(i, j, ++cnt);
}
void down(int tag)//下落标记为 tag 的连通块
{
    int ans = r + 1;
    for(int i = 1; i <= r; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            if(vis[i][j] == tag)
            {
                int dis = 0;
                while(dis <= r - i && (mp[i + dis][j] == '.' || vis[i + dis][j] == tag)) dis++;
                ans = ans < --dis? ans: dis;
            }
        }
    }
    for(int i = r; i > ans; i--)
    {
        for(int j = 1; j <= c; j++)
        {
            if(vis[i - ans][j] == tag) mp[i - ans][j] = '.', mp[i][j] = 'x';
        }
    }
}
void goal(int height, int side)//射出木棍
{
    int fst = -1;
    for(int i = side == 1? 1: c; i && i <= c; i += side)
    {
        if(mp[height][i] == 'x')
        {
            fst = i;
            break;
        }
    }
    if(!~fst) return;
    mp[height][fst] = '.';
    calc();
//  for(int i = 1; i <= r; i++)
//  {
//      for(int j = 1; j <= c; j++) printf("%d ", vis[i][j]);
//      puts("");
//  }
    int id = -1;
    for(int i = 0; i < 4; i++)
    {
        int nx = height + dx[i], ny = fst + dy[i];
        if(isstone(nx, ny))
        {
            if(~id && id != vis[nx][ny])
            {
//              puts("ff");
                down(id), down(vis[nx][ny]);
                break;
            }
            id = vis[nx][ny];
        }
    }
}
int main()
{
    scanf("%d%d", &r, &c);
    for(int i = 1; i <= r; i++) scanf("%s", mp[i] + 1);
    calc();
    scanf("%d", &n);
    for(int i = 1, height; i <= n; i++)
    {
        scanf("%d", &height);
        height = r - height + 1;
        goal(height, (i & 1)? 1: -1);
//      puts("begin:");
//      for(int ii = 1; ii <= r; ii++) puts(mp[ii] + 1);
//      puts("end.");
    }
    for(int i = 1; i <= r; i++) puts(mp[i] + 1);
    return 0;
}