五子棋.cpp

用c语言写的五子棋算法

#include"stdio.h"
#include"math.h"
#include<stdlib.h>
#include"time.h"
#define N 15

int board[N][N] = {0};//1:黑棋, 2: 白棋, 0:没下的位置, -1:已下的位置
int deal[N * N][3];//待处理点0: x, 1: y;
int n_deal = 0;//待处理点的个数
int max_score_i, max_score_j;//最优下棋点的坐标


/*int flag(int x, int y)//判断是否在棋盘内
{
	return (x >= 0 && x < 15 && y >= 0 && y < 15);
}*/

void find()//找周围未处理的点
{
	int i, j, k, x, y;
	int sign[8][2] = {-1, -1, -1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 0, 1, 1};//相邻的八格
	for (i = 0; i < 15; i++)
		for (j = 0; j < 15; j++)
		{
			if (board[i][j] > 0)
			{
				for (k = 0; k < 8; k++)
				{
					x = i + sign[k][0];
					y = j + sign[k][1];
					if (x >= 0 && x < 15 && y >= 0 && y < 15 && board[x][y] == 0)
					{
						deal[n_deal][0] = x;
						deal[n_deal][1] = y;
						n_deal++;
						board[x][y]=-1;
					}
				}
			}
		}
}
int match(int x, int y, int dx, int dy, int chessman)//逐个打分
{
	int sum = 1;
	int space=0;//空格情况
	int tx = dx, ty = dy;
	while ((x + tx) >= 0 && (x + tx)< 15 && (y + ty) >= 0 && (y + ty) < 15 && board[x + tx][y + ty] == chessman)//找某一方向共有多少个连续的同色
	{
		tx += dx;
		ty += dy;
		sum++;
	}
	if((x + tx) >= 0 && (x + tx)< 15 && (y + ty) >= 0 && (y + ty) < 15 && board[x + tx][y + ty] <= 0){space++;}
    tx = dx, ty = dy;
	while ((x - tx) >= 0 && (x - tx)< 15 && (y - ty) >= 0 && (y - ty) < 15  && board[x - tx][y - ty] == chessman)//沿相应的负方向搜索
	{
		tx += dx;
		ty += dy;
		sum++;
	}
	if((x - tx) >= 0 && (x - tx)< 15 && (y - ty) >= 0 && (y - ty) < 15 && board[x - tx][y - ty] <= 0) {space++;}

	if(sum>=5)                  return 1000000;
	if(sum>=4 && space>=2)      return 100000;
    if (sum >= 4 && space >= 1) return 15000;
	if (sum >= 3 && space >= 2) return 10000;
	if (sum >= 3 && space >= 1) return 1000;
	return 100;
}
int score()//打分
{
	int x, y,s;
	int i, j, t,k=0;
	int max_value = 0;
	int sign[4][2] = {1, 0, 0, 1, 1, 1, 1, -1};
	for (i = n_deal - 1; i >= 0; i--)
	{
		x = deal[i][0];
		y = deal[i][1];
		t = 0;
		for (j = 0; j < 4; j++)//分别从四个方向搜索
		{
			t += match(x, y, sign[j][0], sign[j][1], 1);
			t += match(x, y, sign[j][0], sign[j][1], 2);
		}
	   if (t > max_value)
		{
			max_value = t;
			deal[i][2]=max_value;//
			t=i;//
			max_score_i = x;
			max_score_j = y;
		}
	}
	s=deal[t][2]/10;
    for (i = 0; i <= n_deal - 1; i++)
		if(deal[t][3]-deal[i][2]<s)
		{
            deal[k][0]=deal[i][0];
			deal[k][1]=deal[i][1];
			k++;
		}
	i=rand()%k;//
	return i;
}

void main()
{
	int n, i, x, y;
	scanf("%d",&n);
	if (n == 0)
		printf("7,7"); //输出棋盘中点
	for (i = 0; i < n; i++)
	{
		scanf("%d,%d", &x, &y);
		board[x][y] = i % 2 + 1;//对以下的点进行标记(1:黑,2:白)
	}
	srand((unsigned int)time(NULL));
	find();
	n=score();
	//printf("%d,%d", max_score_i, max_score_j);
	printf("%d,%d",deal[n][0],deal[n][1]);
	
}