用C++程序解决星星碰问题
04/291 浏览综合
#include <iostream>
using namespace std;
int map[100][100];
int ans[100][100];
int n,m;
bool check_map(){
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(map[i][j]==1)return false;
return true;
}
void change_light(int x,int y){
if(map[x][y]>=0)map[x][y]^=1;
if(map[x+1][y]>=0)map[x+1][y]^=1;
if(map[x][y+1]>=0)map[x][y+1]^=1;
if(map[x-1][y]>=0)map[x-1][y]^=1;
if(map[x][y-1]>=0)map[x][y-1]^=1;
}
bool dfs(int x,int y){
if(x>n){
return check_map();
}
if(y>m){
return dfs(x+1,1);
}
if(map[x][y]==-1)return dfs(x,y+1);
// test 0:
ans[x][y]=0;
bool ans2 = dfs(x,y+1);
if(ans2)return true;
// test 1:
ans[x][y]=1;
change_light(x,y);
ans2 = dfs(x,y+1);
if(ans2)return true;
change_light(x,y);
ans[x][y]=0;
return false;
}
int main(){
cin>>n>>m;
char c;
for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++)map[i][j]=-1;
for(int i=1;i<=n;i++){
string str;
cin>>str;
for(int j=1;j<=m;j++){
c= str[j-1];
if(c=='#')map[i][j]=-1;
if(c=='*')map[i][j]=1;
if(c=='.')map[i][j]=0;
}
}
dfs(1,1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(map[i][j]<0)cout<<"#";
else cout<<ans[i][j];
}
cout<<endl;
}
}
先输入行数和列数
然后输入地图，点表示空格，*表示星星，# 表示墙壁。注意地图外的格子需要全部标成墙壁。
然后程序会输出一个相同大小的包含0，1和# 的answer，表示解法。0表示该格子需要按偶数遍，如果没有星星可以把相邻的按一下然后这个点按两次。1表示该格子需要按奇数遍。
实测任何游戏中的题都可以用该程序间接解决
