磨棋盘算法

❶ 棋盘覆盖问题的算法分析

设T(k)是算法ChessBoard覆盖一个2^k×2^k棋盘所需时间，从算法的划分
策略可知，T(k)满足如下递推式：
T(k) = 1 当k=0时
T(k) = 4T(k-1) 当k>0时
解此递推式可得T(k)=O(4^k)。

❷ 求8x8棋盘完美覆盖的算法

当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。

❸ 一道棋盘算法问题！用（c++）

真巧，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>
#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;
}

❹ 棋盘覆盖问题的算法实现

下面讨论棋盘覆盖问题中数据结构的设计。
（1）棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中，size=2^k。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量；
（2）子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示；
（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标;
（4） L型骨牌：一个2^k×2^k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4^k-1)/3，将所有L型骨牌从1开始连续编号，用一个全局变量t表示。
设全局变量t已初始化为0，分治法求解棋盘覆盖问题的算法用C++语言描述如下：
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
int s, t1; //t1表示本次覆盖所用L型骨牌的编号
if (size == 1) return; //棋盘只有一个方格且是特殊方格
t1 = ++t; // L型骨牌编号
s = size/2; // 划分棋盘
if (dr < tr + s && dc < tc + s) //特殊方格在左上角子棋盘中
ChessBoard(tr, tc, dr, dc, s); //递归处理子棋盘
else{ //用 t1号L型骨牌覆盖右下角，再递归处理子棋盘
board[tr + s - 1][tc + s - 1] = t1;
ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
}
if (dr < tr + s && dc >= tc + s) //特殊方格在右上角子棋盘中
ChessBoard(tr, tc+s, dr, dc, s); //递归处理子棋盘
else { //用 t1号L型骨牌覆盖左下角，再递归处理子棋盘
board[tr + s - 1][tc + s] = t1;
ChessBoard(tr, tc+s, tr+s-1, tc+s, s);
}
if (dr >= tr + s && dc < tc + s) //特殊方格在左下角子棋盘中
ChessBoard(tr+s, tc, dr, dc, s); //递归处理子棋盘
else { //用 t1号L型骨牌覆盖右上角，再递归处理子棋盘
board[tr + s][tc + s - 1] = t1;
ChessBoard(tr+s, tc, tr+s, tc+s-1, s);
}
if (dr >= tr + s && dc >= tc + s) //特殊方格在右下角子棋盘中
ChessBoard(tr+s, tc+s, dr, dc, s); //递归处理子棋盘
else { //用 t1号L型骨牌覆盖左上角，再递归处理子棋盘
board[tr + s][tc + s] = t1;
ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
}
}

❺ 马踏棋盘算法

#include <stdio.h>
main()
{
int a[9][9],object[9][9],step[9][3]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},
{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1}};
int i,j,k,x,y,z,m,n,min;
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
a[i][j]=0; /* clear data in array */
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
for(k=1;k<=8;k++)
{
x=i;y=j;
x=x+step[k][1];
y=y+step[k][2];
if(x>=1&&x<=8&&y>=1&&y<=8)
a[i][j]++ ; /* initilize array */
} /* start col and row;*/
printf("Please inpute start position x,y\n");
scanf("%d,%d",&m,&n);
for(z=1;z<=64;z++)
{
min =10;
object[m][n]=z;
a[m][n]=0;
for(k=1;k<=8;k++)
{
x=m+step[k][1];
y=n+step[k][2];
if(x>=1&&x<=8&&y>=1&&y<=8)
if(a[x][y]!=0)
{
--a[x][y];
if(a[x][y]<min)
{
min=a[x][y];
i=x;
j=y;
}
}
}
m=i;n=j;
}
for(i=1;i<=8;i++)
{
for(j=1;j<=8;j++)
printf("%6d",object[i][j]);
printf("\n");
}
}
请采纳答案，支持我一下。

❻ 机器人走棋盘算法采用的什么控制结构

循环结构

_馐且桓黾虻サ纳嬗蜗罚憧刂埔桓龌魅舜右桓銎迮痰钠鹗嫉?(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下：

? 1.机器人一开始在棋盘的起始点并有起始点所标有的能量。

? 2.机器人只能向右或者向下走，并且每走一步消耗一单位能量。

? 3.机器人不能在原地停留。

? 4.当机器人选择了一条可行路径后，当他走到这条路径的终点时，他将只有终点所标记的能量。

❼ 现在所有的围棋算法，尽量全一点

有两种新型的树算法，我在围棋天地上看到过，欧洲人发现的，因为这两种算法，电脑棋力提升了一大截，你可以找找。

❽ 中国象棋中怎么算做磨棋

你觉得磨的，都是磨棋

❾ 棋盘覆盖算法

import java.util.*;

public class TestChessBoard {
public static void main(String[] args) {
int tr=0,tc=0,dr=1,dc=2,size=8;
ChessBoard.chessBoard(tr,tc,dr,dc,size);
ChessBoard.display();
}
}

class ChessBoard {
public static int tile = 0;
public static int[][] board= new int[10][10];
public static void chessBoard (int tr,int tc,int dr,int dc,int size) {

if(size == 1) return;
int t = tile++ , s = size/2;
if(dr<tr+s && dc<tc+s){
chessBoard(tr,tc,dr,dc,s);
}else {
board[tr+s-1][tc+s-1] = t;
chessBoard(tr,tc,tr+s-1,tc+s-1,s);
}

if(dr<tr+s && dc>=tc+s){
chessBoard(tr,tc+s,dr,dc,s);
}else {
board[tr+s-1][tc+s] = t;
chessBoard(tr,tc+s,tr+s-1,tc+s,s);
}

if(dr>=tr+s && dc<tc+s) {
chessBoard(tr+s,tc,dr,dc,s);
}else {
board[tr+s][tc+s-1] = t;
chessBoard(tr+s,tc,tr+s,tc+s-1,s);
}

if(dr>=tr+s && dc>=tc+s) {
chessBoard(tr+s,tc+s,dr,dc,s);
}else {
board[tr+s][tc+s] = t;
chessBoard(tr+s,tc+s,tr+s,tc+s,s);
}
}

public static void display() {
for(int i=0;i<8;i++){
for(int j=0;j<8;j++) {
System.out.print(" "+board[i][j]);
}
System.out.println();
}
}
}

❿ 棋盘人工智能算法

即可吃掉对方的子？
不应该是这样的吧！我想应该是 满足条件即可收回自己的子，然后到一方没有子可放置为止！

you are so mean! 太没有诚意了吧 哈哈~~~
高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？高手在哪里？？？？ ....