备战 清华大学 上机编程考试-冲刺前50%,倒数第3天

T1:水滴 - 模拟

这是一个经典的游戏。

在一个 𝑛×𝑚 的棋盘上，每一个格子中都有一些水滴。

玩家的操作是，在一个格子中加一滴水。

当一个格子中的水滴数超过了 4，这一大滴水就会因格子承载不住而向外扩散。扩散的规则是这样的：

这个格子中的水滴会消失，然后分别向上、左、下、右 4 个方向发射一个水滴。如果水滴碰到一个有水的格子，就会进入这个格子。否则水滴会继续移动直到到达棋盘边界后消失。扩散后，水滴进入新的格子可能导致该格子的水滴数也超过 4 ，则会立即引发这个格子的扩散。我们规定，每个格子按逆时针顺序从上方向开始，递归处理完每一个方向的扩散以及其引发的连锁反应，再处理下一个方向的扩散。

给定棋盘的初始状态和玩家的操作，求最后水滴的分布情况。

由于把水滴在一个空格看起来用处不大，所以保证所有的玩家操作都不会选择空格。

提示：可以记录每个水滴上下左右方向第一个水滴的位置，扩散时根据规则模拟，并在每次操作后维护。

输入格式：

从标准输入读入数据。

第一行四个整数 𝑛,𝑚,𝑐,𝑇。

接下来 𝑐 行，每行三个正整数 𝑥𝑖,𝑦𝑖,𝑎𝑖，表示初始棋盘上第 𝑥𝑖 行 𝑦𝑖 列有 𝑎𝑖 个水滴。

接下来 𝑇 行，每行两个正整数 𝑢𝑖,𝑣𝑖，表示在第 𝑢𝑖 行 𝑣𝑖 列放入一个水滴。

输出格式：

输出到标准输出。

输出 𝑇 加若干行。

前 𝑇 行每行一个整数，第 𝑖 行表示在第 𝑖 次操作后扩散的水滴数。若没有扩散输出 0。

最后若干行（可能是 0 行）表示棋盘上水滴的分布情况。由上至下，由左至右输出，每行三个正整数表示行号、列号、水滴数。

解：

关键是模拟,模拟选择好 对应的 数据结构 + 合理的状态设置、记录 + 递归涉及(递归的前后次序) + if判断情况考虑全面:

code:

//水滴：大模拟
//似乎又是模拟问题， 我觉得那个老哥的经验贴说得对！-就是模拟 + 搜索 + 动态规划
//dfs ,bfs 深度优先 和 广搜 ——>记得用leetcode复习！#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<string>using namespace std;//虽然有点大，不过似乎可以用 vector<vector<int> > vec(n,vector(m,0))
int n,m,c,T;int mycount; //记录一次 滴水 发生的 扩散的次数//感觉不难，主要是如何记录，直接递归大模拟搞定：
vector<vector<int> > vec;
vector<vector<int> > flag; //记录状态0-4void init()
{//处理输入:cin>>n>>m>>c>>T;vector<vector<int> > vec2(n+1,vector<int>(m+1,0));  //下标从1开始用vec = vec2;    //记录全局水滴数flag = vec2;   //记录全局状态while(c--){int num1,num2,num3;cin>>num1>>num2>>num3;vec[num1][num2] = num3;      }
}void func(int x, int y , int destination)  //在(x,y)位置 滴水1次
{//另外一个出口 —— 出界:if(x < 1 || x > n || y < 1 || y > m){return ; //出界了，不管了}if(vec[x][y] == 0 || flag[x][y] != 0)  //没水，或者就是扩散状态{//进入这里，只可能是扩散递归的情况://不坐停留，直接调用 下一层 递归 并且 return//似乎还要一个方向参数：if(destination == 1){func(x-1,y,1);}else if(destination == 2){func(x,y-1,2);}else if(destination == 3){func(x+1,y,3);}else if(destination == 4){func(x,y+1,4);}return ;}vec[x][y] +=1;    //此处原来至少1滴水if(vec[x][y] > 4){//发生扩散：mycount++;//设置状态flag[x][y] = 1; //并且进行依次 2 ，3 ，4 ，0 状态，递归://递归出口就是 最后的状态0vec[x][y] = 0;flag[x][y] = 1; //进入 UP状态func(x-1,y,1);    //递归，上面那个+1//--递归退出：flag[x][y] = 2; //进入 Left状态func(x,y-1,2);//--递归退出:flag[x][y] = 3; //进入Down状态func(x+1,y,3);   //--递归退出:flag[x][y] = 4; //进入Right状态func(x,y+1,4);//--递归退出：flag[x][y] = 0 ; //恢复平静}
}//有一点一定要注意，那就是，只要这个vec[x][y] ==0 
//只要第一次 没有水滴， 或者 之后这个位置发送了 1次 扩散
//那么， 之后 这个位置就不可能再有水滴！！！！ -- 可以优化地方int main()
{init();////进行T次滴水，调用T次-递归函数funcwhile(T--){//滴水一次！mycount = 0; //归零int num1,num2;cin>>num1>>num2;func(num1,num2,1);//进行输出 -- 总共有地方 水滴 > 4cout<<mycount<<endl;}//最终的输出:for(int i = 1 ;i <= n;i++){for(int j  = 1; j<=m ;j++){if(vec[i][j] != 0 ){cout<<i<<" "<<j<<" "<<vec[i][j]<<endl;}}}return 0;
}