UC知道5*5棋盘问题C++
来源：百度知道 编辑：UC知道 时间：2024/07/05 07:20:59
在5*5棋盘的横竖交叉点上放黑棋子，已放黑棋子点上下左右相邻的点不能再放白子。编程找出放置6个黑子能控制整个棋盘的所有方案,并打印出黑子的位置。
#include<iostream>
using namespace std;
const int size = 5;
class MAP
{
public:
void clear( );
void solve( int, int, int, int );
void print( );
private:
void copywhite( );
bool place[ size + 2 ][ size + 2 ];
bool whiteplace[ size + 2 ][ size + 2 ];
bool Minwhiteplace[ size + 2 ][ size + 2 ];
int Min;
};
void MAP::clear( )
{
memset( place, 1, sizeof( place ) );
memset( whiteplace, 0, sizeof( whiteplace ) );
memset( Minwhiteplace, 0, sizeof( Minwhiteplace ) );
Min = size * size;
}
void MAP::copywhite( )
{
int i, j;
for ( i = 1; i <= size; i++ )
for ( j = 1; j <= size; j++ )
Minwhiteplace[ i ][ j ] = whiteplace[ i ][ j ];
}
void MAP::solve( int t, int line, int count, int lie )
{
if ( t &l
#include<iostream>
using namespace std;
const int size = 5;
class MAP
{
public:
void clear( );
void solve( int, int, int, int );
void print( );
private:
void copywhite( );
bool place[ size + 2 ][ size + 2 ];
bool whiteplace[ size + 2 ][ size + 2 ];
bool Minwhiteplace[ size + 2 ][ size + 2 ];
int Min;
};
void MAP::clear( )
{
memset( place, 1, sizeof( place ) );
memset( whiteplace, 0, sizeof( whiteplace ) );
memset( Minwhiteplace, 0, sizeof( Minwhiteplace ) );
Min = size * size;
}
void MAP::copywhite( )
{
int i, j;
for ( i = 1; i <= size; i++ )
for ( j = 1; j <= size; j++ )
Minwhiteplace[ i ][ j ] = whiteplace[ i ][ j ];
}
void MAP::solve( int t, int line, int count, int lie )
{
if ( t &l
真巧，pku 1753就是这题。。
前几天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>
#incl