心路历程根据题面的描述 , 我们面临的问题无非是,每次将色块更新成什么颜色 。又因为是从左上角开始更新,所以我的有了第一个想法 。
将左上角的色块命名为“原色块” 。
对于每个色块,定义4中状态:0-不属于原色块势力 , 和原色块势力不邻接,未没有进行任何操作;1-不属于原色块势力 , 和原色块势力邻接,尚不知道会不会被同化(因为还不知道下一步染什么色);2-属于原色块势力,和非原色块势力邻接,是上一批被同化的色块;3-属于原色块势力,和非原色块势力不邻接**;
我们可以形象地依次把这四种状态称作“未加入”,“待审核”,“新成员”,“老成员” 。以下图为例(颜色是色块,数字是状态):
![flood_it 方法记录](http://img.zhejianglong.com/231018/0625401415-0.png)
文章插图
第一步比较特殊,因为需要求出最初的新队员 。(之后就只需要处理新成员和待审核就可以了 , 因为新成员处于邻接位置,需要承担审核工作 。而老成员和未加入不需要做任何工作)
首先原色块自身是新成员,然后跑一遍bfs,求出所有与原色块连通且与原色块同色的色块 , 将它们都标记为新成员 。
之后的每一步,首先统计与新成员邻接且未加入的色块,将它们标记为待审核,并统计每种颜色出现的次数 。
出现次数最多的颜色就是我们即将更新的颜色 。得到这个之后新成员的工作就做完了,新成员就可以标记为老成员了 。
再次遍历所有待审核的色块 , 若颜色和即将更新的颜色相同,则标记为新成员;否则重新标记为未加入 。
【flood_it 方法记录】将所有新成员、老成员的颜色更新 。
每次都需要判断是否更新完整个图 。
这个算法逻辑上是行得通的,但是太慢了 , 因为要反复地遍历各种状态,导致大量无用的重复运算 。
正解标算:IDA*先不谈IDA* 。我们回到这道题,从模块化编程的角度出发,想想这个程序要实现什么功能 。
首先我们有更新色块的操作 。对于更新色块的函数,我们需要3个形参:当前色块的横坐标、纵坐标、我们即将更新的颜色 。我们仍然需要一个打标记的数组:若当前位置的颜色和即将更新的颜色相同则标记为1 , 反之则标记为2.所以这个函数的主要功能是给需要更新颜色的色块打标记,还没有进行上色操作 。
void update_flags(int i,int j,int color)//color是即将更新的颜色{if(board[i][j]!=color){flags[i][j]=2;//和即将更新的颜色不同,打上标记2return ;}flags[i][j]=1;//和即将更新的颜色相同,打上标记1for(int k=0;k<4;k++){//dir[][]用于枚举4个方向int x=i+dir[k][0];int y=j+dir[k][1];if(x<0||y<0||x>=siz||y>=siz||flags[x][y]) continue;update_flags(x,y,color);//递归更新尚未打标记的色块}}
然后考虑具体的上色操作 。最外层循环遍历6种颜色 , 然后遍历全图 。若当前遍历到的位置是不同颜色且正好等于要搜索的颜色,则记录存在这种颜色,并进行\(update_flags\).若全图遍历完后发现不存在这种颜色 , 则继续遍历下一个颜色 。如果更新了棋盘,就递归搜索,成功了就返回 。注意:\(flags\)数组在这个过程中可能会被改变,为了后续的使用,我们需要在操作前拷贝\(flags\)到\(tmp\)数组,操作结束后再拷贝回去 。接下来再考虑使用IDA
推荐阅读
- 江南百景图前往猎户人家后山方法是什么
- 【对讲机怎么用】对讲机正确使用方法(对讲机如何正确使用)
- 对讲机怎么用对讲机使用方法图解(对讲机喊话键下面俩键干什么用的)
- 对讲机使用操作方法(gp338d对讲机使用说明)
- 对讲机怎么正确使用(中继对讲机使用方法图解)
- 【博学谷学习记录】超强总结,用心分享|MySql连接查询超详细总结
- 小米电视怎么一键看电视直播(小米电视看直播台方法)
- 我的世界附魔书使用方法我的世界附魔书怎么用
- steam好友功能怎么用steam好友添加方法
- 红米note11Pro怎么设置5G_设置5G网络方法