做题感悟:这题很有意思,开始做时根本没想太多,做了一个晚上也没做出来,但是昨天一看晚上突然想到一种方法,灵感来时挡也挡不住啊!
解题思路:这题时间必须同步更新,so~ 应该用bfs 比较好,用bfs 模拟水滴爆裂,怎样模拟呢? 需要将飞行的水滴放进一个队列,取出时将所有的飞行的水滴都取出同步更新所有点,这里可能要设置两个队列,一个存储以前的水滴,一个存储下一秒的水滴,之后再将下一秒的水滴存入上一秒的队列(这可能不好想,就是设置两个队列,辅队列暂时存下一秒的飞行的水滴,之后还要将其全部转入主队列,如果还是不懂请结合代码理解)。
代码:
#include<stdio.h> #include<iostream> #include<map> #include<stack> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; #define lld __int64 const double PI = 3.1415926 ; const double esp = 1e-4 ; const int md= 2810778 ; const int MX = 10 ; int g[MX][MX] ; int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1} ; struct node { int x,y,ct ; // ct 标记方向 } ; bool search(int x,int y) { if(x<0||y<0||x>=6||y>=6) return false ; return true ; } void bfs(int x,int y) { int ct,sx,sy ; queue<node>q ;// 主队列 queue<node>p ;// 辅队列 node curt,next ; curt.x=x ; curt.y=y ; for(int i=0 ;i<4 ;i++) // 爆裂的水滴向四个方向飞去 { curt.ct=i ; // 方向 q.push(curt) ; } while(!q.empty()) // 还存在飞行的水滴 { while(!q.empty()) // 全部取出来都在自己方向上走一步 { curt=q.front() ; q.pop() ; x=curt.x ; y=curt.y ; ct=curt.ct ; next.x=sx=curt.x+dx[ct] ; next.y=sy=curt.y+dy[ct] ; next.ct=ct ; if(!search(sx,sy)) continue ; // 限界条件 if(g[sx][sy]) // 遇到水滴 g[sx][sy]++ ; else // 空的格子 p.push(next) ; //先存入辅助格子 } for(int i=0 ;i<6 ;i++) // 检查是否有大于 4 的水滴 for(int j=0 ;j<6 ;j++) if(g[i][j]>4) // 爆裂 { g[i][j]=0 ; curt.x=i ; curt.y=j ; for(int k=0 ;k<4 ;k++) // 向四个方向飞去 { curt.ct=k ; // 方向 q.push(curt) ; } } while(!p.empty()) // 将辅队列的水滴放进主队列 { curt=p.front() ; p.pop() ; q.push(curt) ; } } } int main() { int x,y,m ; while(~scanf("%d%d%d%d%d%d",&g[0][0],&g[0][1],&g[0][2],&g[0][3],&g[0][4],&g[0][5])) { for(int i=1 ;i<6 ;i++) for(int j=0 ;j<6 ;j++) scanf("%d",&g[i][j]) ; scanf("%d",&m) ; for(int i=0 ;i<m ;i++) { scanf("%d%d",&x,&y) ; x-- ; y-- ; if(g[x][y]==4) // 如果满足爆裂条件 { g[x][y]=0 ; bfs(x,y) ; } else g[x][y]++ ; // 不满足加一 } for(int i=0 ;i<6 ;i++) // 输出 { for(int j=0 ;j<6 ;j++) if(!j) printf("%d",g[i][j]) ; else printf(" %d",g[i][j]) ; printf("\n") ; } printf("\n") ; } return 0 ; }