微信网站怎么做的好名字吗,做数据表格的网站,运城网站建设维护,asp汽车驾驶培训学校网站源码T1:水滴 - 模拟
这是一个经典的游戏。
在一个 #x1d45b;#x1d45a; 的棋盘上#xff0c;每一个格子中都有一些水滴。
玩家的操作是#xff0c;在一个格子中加一滴水。
当一个格子中的水滴数超过了 4#xff0c;这一大滴水就会因格子承载不住而向外扩散。扩散的规…T1:水滴 - 模拟
这是一个经典的游戏。
在一个 × 的棋盘上每一个格子中都有一些水滴。
玩家的操作是在一个格子中加一滴水。
当一个格子中的水滴数超过了 4这一大滴水就会因格子承载不住而向外扩散。扩散的规则是这样的
这个格子中的水滴会消失然后分别向上、左、下、右 4 个方向发射一个水滴。如果水滴碰到一个有水的格子就会进入这个格子。否则水滴会继续移动直到到达棋盘边界后消失。扩散后水滴进入新的格子可能导致该格子的水滴数也超过 4 则会立即引发这个格子的扩散。我们规定每个格子按逆时针顺序从上方向开始递归处理完每一个方向的扩散以及其引发的连锁反应再处理下一个方向的扩散。
给定棋盘的初始状态和玩家的操作求最后水滴的分布情况。
由于把水滴在一个空格看起来用处不大所以保证所有的玩家操作都不会选择空格。
提示可以记录每个水滴上下左右方向第一个水滴的位置扩散时根据规则模拟并在每次操作后维护。
输入格式
从标准输入读入数据。
第一行四个整数 ,,,。
接下来 行每行三个正整数 ,,表示初始棋盘上第 行 列有 个水滴。
接下来 行每行两个正整数 ,表示在第 行 列放入一个水滴。
输出格式
输出到标准输出。
输出 加若干行。
前 行每行一个整数第 行表示在第 次操作后扩散的水滴数。若没有扩散输出 0。
最后若干行可能是 0 行表示棋盘上水滴的分布情况。由上至下由左至右输出每行三个正整数表示行号、列号、水滴数。
解
关键是模拟,模拟选择好 对应的 数据结构 合理的状态设置、记录 递归涉及(递归的前后次序) if判断情况考虑全面:
code:
//水滴大模拟
//似乎又是模拟问题 我觉得那个老哥的经验贴说得对-就是模拟 搜索 动态规划
//dfs ,bfs 深度优先 和 广搜 ——记得用leetcode复习#includeiostream
#includestdio.h
#includestdlib.h
#includealgorithm
#includevector
#includestringusing namespace std;//虽然有点大不过似乎可以用 vectorvectorint vec(n,vector(m,0))
int n,m,c,T;int mycount; //记录一次 滴水 发生的 扩散的次数//感觉不难主要是如何记录直接递归大模拟搞定
vectorvectorint vec;
vectorvectorint flag; //记录状态0-4void init()
{//处理输入:cinnmcT;vectorvectorint vec2(n1,vectorint(m1,0)); //下标从1开始用vec vec2; //记录全局水滴数flag vec2; //记录全局状态while(c--){int num1,num2,num3;cinnum1num2num3;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(x1,y,3);}else if(destination 4){func(x,y1,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(x1,y,3); //--递归退出:flag[x][y] 4; //进入Right状态func(x,y1,4);//--递归退出flag[x][y] 0 ; //恢复平静}
}//有一点一定要注意那就是只要这个vec[x][y] 0
//只要第一次 没有水滴 或者 之后这个位置发送了 1次 扩散
//那么 之后 这个位置就不可能再有水滴 -- 可以优化地方int main()
{init();////进行T次滴水调用T次-递归函数funcwhile(T--){//滴水一次mycount 0; //归零int num1,num2;cinnum1num2;func(num1,num2,1);//进行输出 -- 总共有地方 水滴 4coutmycountendl;}//最终的输出:for(int i 1 ;i n;i){for(int j 1; jm ;j){if(vec[i][j] ! 0 ){couti j vec[i][j]endl;}}}return 0;
}
