题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=3683题目大意:五子棋游戏,计算要在双方均最优情况下,3步棋以内的结果
题解:做这题WA许久的!!!
主要是计算一步必杀时考虑情况不周全。。。
由于只有3步,所以在玩家出动时,可以考虑:
1.该玩家否一招胜利(如果是,直接胜利);
2.面临被对方灭(拿棋子档)
双方均按照这个逻辑下棋
还有一种情况是当先手下棋后,无论对方怎么走都得赢,有四子一线,二分阵和三分阵。
代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dsx[4] =
{1,1,0,-1};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dsy[4] =
{0,1,1,1};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int L = 15;
int m;
int board[16][16];
int front;
int next;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool Judge(int color,int x,int y)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
for(int k = 0; k < 4; ++k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int ti = x + dsx[k];
int tj = y + dsy[k];
int cnt1 = 0;
int cnt2 = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while((ti >= 0 && ti < L)&&(tj >= 0 && tj < L))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(board[ti][tj] == color)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
++cnt1;
ti += dsx[k];
tj += dsy[k];
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
break;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ti = x - dsx[k];
tj = y - dsy[k];
if((ti >= 0 && ti < L)&&(tj >= 0 && tj < L))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
while((ti >= 0 && ti < L)&&(tj >= 0 && tj < L))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(board[ti][tj] == color)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
++cnt2;
ti -= dsx[k];
tj -= dsy[k];
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
break;
}
}
}
if(cnt1 + cnt2 >= 4)
return true;
}
return false;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool JudgeSureWin(int color,int x,int y)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int arrCnt = 0;//阵势计数
for(int k = 0; k < 4; ++k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int nx = x + dsx[k];
int ny = y + dsy[k];
int rCnt = 0;
int lCnt = 0;
bool rCan = false;
bool lCan = false;
int rrCnt = 0;
int llCnt = 0;
while(nx >= 0 && ny >= 0 && nx < L && ny < L && board[nx][ny] == color)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
rCnt ++;
nx += dsx[k];
ny += dsy[k];
}
if(nx >= 0 && ny >= 0 && nx < L && ny < L && board[nx][ny] == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
rCan = true;
//计算rr
nx += dsx[k];
ny += dsy[k];
while(nx >= 0 && ny >= 0 && nx < L && ny < L && board[nx][ny] == color)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
rrCnt ++;
nx += dsx[k];
ny += dsy[k];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
nx = x - dsx[k];
ny = y - dsy[k];
while(nx >= 0 && ny >= 0 && nx < L && ny < L && board[nx][ny] == color)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
lCnt ++;
nx -= dsx[k];
ny -= dsy[k];
}
if(nx >= 0 && ny >= 0 && nx < L && ny < L && board[nx][ny] == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
lCan = true;
//计算rr
nx -= dsx[k];
ny -= dsy[k];
while(nx >= 0 && ny >= 0 && nx < L && ny < L && board[nx][ny] == color)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
llCnt ++;
nx -= dsx[k];
ny -= dsy[k];
}
}
//四子连线
if((lCan && rCan) && (lCnt + rCnt >= 3))
return true;
//二分阵
if((lCnt + rCnt >= 3)&&(lCnt || rCnt))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
arrCnt ++;
continue;
}
//三分阵
if((lCnt + rCnt + llCnt >= 3) || (lCnt + rCnt + rrCnt) >= 3)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
arrCnt++;
continue;
}
}
return (arrCnt >= 2);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool OneMoveWin(int color,int &_rx,int& _ry)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
for(int i = 0; i < L; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(int j = 0; j < L ; ++j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(board[i][j] == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(Judge(color,i,j))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
_rx = i;
_ry = j;
return true;
}
}
}
}
return false;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool JudgeSure(int color,int &_rx,int& _ry)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
for(int i = 0; i < L; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(int j = 0; j < L; ++j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(board[i][j] == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(JudgeSureWin(color,i,j))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
_rx = i;
_ry = j;
return true;
}
}
}
}
return false;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Test()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
memset(board,0,sizeof(board));
int x,y,ci;
int blackCnt = 0;
int whiteCnt = 0;
for(int i = 0; i < m; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d %d %d",&x,&y,&ci);
board[x][y] = ci+1;
if(ci == 0)
whiteCnt++;
else
blackCnt++;
}
if(whiteCnt == blackCnt)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
front = 2;
next = 1;
}
else if(blackCnt == whiteCnt + 1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
front = 1;
next = 2;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("Invalid.\n");
return ;
}
int px1 = -1,py1 = -1;
int px2 = -1,py2 = -1;
int px3 = -1,py3 = -1;
//begin judge
if(OneMoveWin(front,px1,py1))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(front == 1)
printf("Place white at (%d,%d) to win in 1 move.\n",px1,py1);
else
printf("Place black at (%d,%d) to win in 1 move.\n",px1,py1);
}
else if(OneMoveWin(next,px1,py1))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
//help
board[px1][py1] = front;
if(OneMoveWin(next,px2,py2))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("Lose in 2 moves.\n");
}
else if(OneMoveWin(front,px2,py2))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
//help
board[px2][py2] = next;
if(OneMoveWin(front,px3,py3))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(front == 1)
printf("Place white at (%d,%d) to win in 3 moves.\n",px1,py1);
else
printf("Place black at (%d,%d) to win in 3 moves.\n",px1,py1);
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("Cannot win in 3 moves.\n");
}
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("Cannot win in 3 moves.\n");
}
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(JudgeSure(front,px1,py1))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(front == 1)
printf("Place white at (%d,%d) to win in 3 moves.\n",px1,py1);
else
printf("Place black at (%d,%d) to win in 3 moves.\n",px1,py1);
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("Cannot win in 3 moves.\n");
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while(scanf("%d",&m)!= EOF,m > 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
Test();
}
return 0;
}
posted on 2010-11-11 14:02
bennycen 阅读(436)
评论(2) 编辑 收藏 引用 所属分类:
算法题解