棋谱算法
‘壹’ 围棋点目怎么算
围棋点目算法有两种：数子法和计目法
1、计目（比目）法：用简单的文字表述，就是计算比较双方终局时所围的地域目数，并以目数多少来判断胜负结果，日韩围棋规则都采用计目法。而中国的围棋规则则是采用数子法。
2、数子法是根据棋局终局后对局双方的棋子在棋盘上所归属位点的多少来计算判断胜负结果的。
计目法由于只计算所围的地域目数，收完单官与否并不影响胜负结果，因而规定棋局终局不收单官。所以是否收完所有单官，是数子法和计目法在终局时的主要区别。
所谓归本数，是指数子法的基础胜负标准。因为标准围棋棋盘总计有361个交叉点，所以对局双方每方应得点数应为总点数的一半，即180.5点。多于此数者胜，少于此数者败，等于此数者和。
(1)棋谱算法扩展阅读：
一、基本下法
对局双方各执一色棋子，黑先白后，交替下子，每次只能下一子。
棋子下在棋盘上的交叉点上。
棋子落子后，不得向其他位置移动。
轮流下子是双方的权利，但允许任何一方放弃下子权而使用虚着。
二、棋子的气：一个棋子在棋盘上，与它直线紧邻的空点是这个棋子的“气”。棋子直线紧邻的点上，如果有同色棋子存在，则它们便相互连接成一个不可分割的整体。
它们的气也应一并计算。棋子直线紧邻的点上，如果有异色棋子存在，这口气就不复存在。如所有的气均为对方所占据，便呈无气状态。无气状态的棋子不能在棋盘上存在，也就是——提子。
三、提子：把无气之子提出盘外的手段叫“提子”。提子有二种：
1、下子后，对方棋子无气，应立即提取。
2、下子后，双方棋子都呈无气状态，应立即提取对方无气之子。拔掉对手一颗棋子之后，就是禁着点（也叫禁入点）。棋盘上的任何一子，如某方下子后，该子立即呈无气状态，同时又不能提取对方的棋子，这个点，叫做“禁着点”，禁止被提方下子。
‘贰’ 棋盘最小路径问题的算法
f[i,j]=min(f[i-1][j],f[i][j-1])+这个格的数字
(f[i,j]表示由1,1到i,j这个格的最小权和.
‘叁’ 求8x8棋盘完美覆盖的算法
如果用1*2覆盖的话
任意一块骨牌在棋盘上的摆放都可以用一串长度为64的0、1序列来表示，比如
……0——>表示在棋盘最左上角的位置横着摆上一块骨牌。
考虑到骨牌既可以横着摆也可以竖着摆，一块骨牌在棋盘上的摆放共有2*7*8=112种情况.
这样就可以得到一个112*60大小的矩阵，不妨将该矩阵记为A。矩阵中的元素由0和1组成，矩阵中的每一行都有且只有两个1。
于是上述问题，就转换成怎样从矩阵中找出32行，抽取出来的这32行构成的新的32*60的矩阵，如果能满足每列中有且只有一个1，那么它就是一个完美覆盖。
矩阵的算法如下：
如果矩阵A为空且已经选出了32行，则找到一个完美覆盖，成功返回；
否则选取一个列c，如果c列中不存在1的话，不成功返回;
选择C列中每一个满足A[r,c]=1的行r;
将r值作为解决方案的一个步骤记录下来；
对于r行中每一个A[r,j]=1的j值，从矩阵A中将第j列删除;
对于j列中每一个A[i,j]=1的i值，从矩阵A中将第i行删除;
将已经缩小的矩阵重复进行上面的运算。
‘肆’ 马踏棋盘算法
#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");
}
}
请采纳答案，支持我一下。
‘伍’ 棋盘覆盖问题的算法分析
设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)。
‘陆’ 一道棋盘算法问题！用（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粒，第二格摆2粒，第三格摆4粒……第六十四格摆2的63次方粒，则共有1+2*2+2*2*2+2*2*2*2+……最后等于（64个2相乘）-1。计算后得1.84x(10的19次方)粒。稻米的千粒重为18-32克，就按25克/千粒计，整个棋盘的米就有4.6x(10的14次方)千克，因此，棋盘摆米按50斤来算一袋共有1.84x(10的13次方)袋。