一道棋盘算法问题!用(c++)
发布网友
发布时间：2022-04-24 18:15
共2个回答
热心网友
时间：2023-10-31 02:07
前几天ICPC训练的时候还写过，现在懒得再写了，要用到bfs，我帮你找到了这题的解题报告，你看看吧：
解题思路：
BFS 即宽搜
因为这题说要找出最小值，也就是求最优值问题，那么，很快就可以想到DP 或者
搜索，而这题很难想出阶段以及状态，所以，构造DP的解法是比较困难的，至于
到底可不可以用DP，我也没有继续深思过，所以，我就想到直接搜索，把所有走法
都模拟出来，然后，哪种走法最快能够实现全盘为白或黑，则答案就出来了！
搜索有BFS和DFS两种，而BFS有能够求出最优值的特点，故考虑用BFS！
方法：
如果把走第i步之前，盘子上所有棋子构成的状态记为S（i-1），并且，初始状态
记为S（0）。而且，可以发现每走一步时，在棋盘上都有4*4=16中选择！但，当
如果盘子上出现的状态在之前也出现过，那么，就可以不用再继续走了！（即剪枝）
我们从第一步开始。。。
把走完第一步后盘子的所有状态都保存起来，如果用
很多个二维数组来保存这些状态就浪费空间了，并且，在之后的要寻找当前状态是否
已经出现过，也会出现麻烦！想一想，因为棋子是黑白两面，可以等价为“0”和“1”
两种性质，那么如果用一个一维数组保存起来的话，例如：
bwwb
bbwb
bwwb
bwww 1001110110011000
那么很快又可以发现另一个特点，图只有2^16个状态。
然后，开一个数组sign[65535]标记已经访问过的状态，则问题就迎刃而解了！
我的程序：
Problem: 1753 User: jlthero
Memory: 504K Time: 32MS
Language: C++ Result: Accepted
Source Code
#include<stdio.h>
#include<string.h>
#include<vector>
#include<iostream>
using namespace std;
char piece[5][5];
int bina[16];
int sign[65536];
int ans;
int toint()
{
int value=0;
int i;
for(i=15;i>=0;i--)
{
value=value*2;
value+=bina[i];
}
return value;
}
void tochar(int n)
{
int i;
for(i=0;i<16;i++)
{
bina[i]=n%2;
n=n/2;
}
}
void slip(int i)
{
bina[i]=1-bina[i];
if(i%4!=0)
bina[i-1]=1-bina[i-1];
if(i%4!=3)
bina[i+1]=1-bina[i+1];
if(i-4>=0)
bina[i-4]=1-bina[i-4];
if(i+4<16)
bina[i+4]=1-bina[i+4];
}
int DFS()
{
vector<int>quene;
int i=0,j;
int value0,value1;
value0=toint();
if(value0==0||value0==65535)
return 0;
else if(sign[value0]==0)
{
quene.push_back(value0);
sign[value0]=1;
}
while(i<quene.size())
{
value0=quene[i];
tochar(value0);
for(j=0;j<16;j++)
{
slip(j);
value1=toint();
if(value1==0||value1==65535)
return sign[value0];
else if(sign[value1]==0)
{
quene.push_back(value1);
sign[value1]=sign[value0]+1;
}
slip(j);
}
i++;
}
return -1;
}
int main()
{
int i,j;
int t,ans;
while(scanf("%s %s %s %s",piece[0],piece[1],piece[2],piece[3])!=EOF)
{
for(i=0;i<4;i++)
{
t=i*4;
for(j=0;j<4;j++)
bina[t+j]=(piece[i][j]=='b'?1:0);
}
memset(sign,0,sizeof(sign));
ans=DFS();
if(ans==-1)
printf("Impossible\n");
else
printf("%d\n",ans);
}
return 0;
}
下面是王炽辉师兄的代码，代码长度要比我短很多^_^：
Problem: 1753 User: wangchi
Memory: 148K Time: 30MS
Language: C Result: Accepted
Source Code
#include<stdio.h>
#include<string.h>
#define MAX 1000000
int a[16], b[16], min;
char ch[4][5];
int legal()
{
int i, t, sum;
static int k = -1;
t = (a[0] + b[0] + b[1] + b[4]) % 2;
for(i = 1; i < 16; i++){
sum = a[i] + b[i];
if(i%4 != 0) sum += b[i-1];
if(i%4 != 3) sum += b[i+1];
if(i-4 >= 0) sum += b[i-4];
if(i+4 < 16) sum += b[i+4];
if(sum % 2 != t) return 0 ;
}
return 1;
}
void dfs(int i, int num)
{
if(i==16) {
if(min > num && legal()) min = num;
return;
}
b[i] = 0;
dfs(i+1, num);
b[i] = 1;
dfs(i+1, num+1);
}
int main()
{
int i, j, t;
while(scanf("%s%s%s%s", ch[0], ch[1], ch[2], ch[3]) != EOF){
for(i = 0; i < 4; i++){
t = i * 4;
for(j = 0; j < 4; j++)
a[t+j] = (ch[i][j]=='w')?0:1;
}
min = MAX;
dfs(0, 0);
if(min == MAX) printf("Impossible\n");
else printf("%d\n", min);
}
return 0;
}
热心网友
时间：2023-10-31 02:07
