- 题目描述:
-
黑白迷阵是一个GrassLand编写的手机游戏,它的规则非常简单,有如下4*5的棋盘,其中一些是格子是黑色,一些格子是白色的,每当点击其中某一个格子,它以及它上下左右五个格子的颜色会发出反转,如下图
游戏胜利的条件很简单,把所有的格子变为黑色即可。
GrassLand想知道,给定一个游戏格局,至少需要几次点击,就可以获得游戏的胜利。
- 输入:
-
输入包含多组测试用例。输入的第一行为一个整数T,代表共有的测试用例数。紧接着为T组测试用例。
每组测试用例,为由四行五列01阵列表示的游戏格局,其中0代表该格子的颜色为白色,1代表该格子的颜色为黑色。
- 输出:
-
对于每组测试用例,输出为一个整数,为至少需要的点击次数。数据保证所给格局可以在有限步内取得胜利。
- 样例输入:
-
2 00111 01111 11111 11111 00111 01111 11110 11100
- 样例输出:
-
1 2
一个比较直观的BFS,重点是要用一个int来表示一个棋盘状态。然后用BFS求解。
我这个直接TLE了,懒得改了,思路反正是对的。
#include<iostream> #include<cstdio> #include<vector> #include<string> #include<cstring> #include<climits> #include<queue> #include<map> #include<algorithm> using namespace std; const int HEIGHT=4; const int WIDTH=5; const int END=(1<<20)-1; int used[END+10]; int step[END+10]; char s[10]; void roll(int x,int y,int& grid) { if(x<0||x>=HEIGHT||y<0||y>=WIDTH) return; int k=(x*WIDTH)+y; grid=grid^(1<<k); } int click(int x,int y,int grid) { int a[]={0,-1,+1,0,0}; int b[]={0,0,0,-1,+1}; for(int i=0;i<5;i++) roll(x+a[i],y+b[i],grid); return grid; } int init() { int k=0; int grid=0; for(int i=0;i<4;i++) { scanf("%s",s); for(int j=0;j<5;j++) { grid|=(s[j]-'0')<<k; k++; } } return grid; } int solve() { int grid=init(); queue<int> Q; Q.push(grid); memset(used,0,sizeof(used)); used[grid]=1; memset(step,0,sizeof(step)); while(!Q.empty()) { int now=Q.front(); Q.pop(); if(now==END) { return step[now]; } for(int x=0;x<4;x++) { for(int y=0;y<5;y++) { int state=click(x,y,now); if(!used[state]) { used[state]=1; step[state]=step[now]+1; Q.push(state); } } } } return 0; } int main() { int t; scanf("%d",&t); while(t--) { int ret=solve(); printf("%d\n",ret); } }