題目鏈接：
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>
int dsx[4] = 
{1,1,0,-1};
int dsy[4] = {0,1,1,1};
const int L = 15;
int m;
int board[16][16];
int front;
int next;
bool Judge(int color,int x,int y)
{
for(int k = 0; k < 4; ++k)
{
int ti = x + dsx[k];
int tj = y + dsy[k];
int cnt1 = 0;
int cnt2 = 0;
while((ti >= 0 && ti < L)&&(tj >= 0 && tj < L))
{
if(board[ti][tj] == color)
{
++cnt1;
ti += dsx[k];
tj += dsy[k];
}
else
{
break;
}
}
ti = x - dsx[k];
tj = y - dsy[k];
if((ti >= 0 && ti < L)&&(tj >= 0 && tj < L))
{
while((ti >= 0 && ti < L)&&(tj >= 0 && tj < L))
{
if(board[ti][tj] == color)
{
++cnt2;
ti -= dsx[k];
tj -= dsy[k];
}
else
{
break;
}
}
}
if(cnt1 + cnt2 >= 4)
return true;
}
return false;
}
bool JudgeSureWin(int color,int x,int y)
{
int arrCnt = 0;//陣勢計數
for(int k = 0; k < 4; ++k)
{
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)
{
rCnt ++;
nx += dsx[k];
ny += dsy[k];
}
if(nx >= 0 && ny >= 0 && nx < L && ny < L && board[nx][ny] == 0)
{
rCan = true;
//計算rr
nx += dsx[k];
ny += dsy[k];
while(nx >= 0 && ny >= 0 && nx < L && ny < L && board[nx][ny] == color)
{
rrCnt ++;
nx += dsx[k];
ny += dsy[k];
}
}
nx = x - dsx[k];
ny = y - dsy[k];
while(nx >= 0 && ny >= 0 && nx < L && ny < L && board[nx][ny] == color)
{
lCnt ++;
nx -= dsx[k];
ny -= dsy[k];
}
if(nx >= 0 && ny >= 0 && nx < L && ny < L && board[nx][ny] == 0)
{
lCan = true;
//計算rr
nx -= dsx[k];
ny -= dsy[k];
while(nx >= 0 && ny >= 0 && nx < L && ny < L && board[nx][ny] == color)
{
llCnt ++;
nx -= dsx[k];
ny -= dsy[k];
}
}
//四子連線
if((lCan && rCan) && (lCnt + rCnt >= 3))
return true;
//二分陣
if((lCnt + rCnt >= 3)&&(lCnt || rCnt))
{
arrCnt ++;
continue;
}
//三分陣
if((lCnt + rCnt + llCnt >= 3) || (lCnt + rCnt + rrCnt) >= 3)
{
arrCnt++;
continue;
}
}
return (arrCnt >= 2);
}
bool OneMoveWin(int color,int &_rx,int& _ry)
{
for(int i = 0; i < L; ++i)
{
for(int j = 0; j < L ; ++j)
{
if(board[i][j] == 0)
{
if(Judge(color,i,j))
{
_rx = i;
_ry = j;
return true;
}
}
}
}
return false;
}
bool JudgeSure(int color,int &_rx,int& _ry)
{
for(int i = 0; i < L; ++i)
{
for(int j = 0; j < L; ++j)
{
if(board[i][j] == 0)
{
if(JudgeSureWin(color,i,j))
{
_rx = i;
_ry = j;
return true;
}
}
}
}
return false;
}
void Test()
{
memset(board,0,sizeof(board));
int x,y,ci;
int blackCnt = 0;
int whiteCnt = 0;
for(int i = 0; i < m; ++i)
{
scanf("%d %d %d",&x,&y,&ci);
board[x][y] = ci+1;
if(ci == 0)
whiteCnt++;
else
blackCnt++;
}
if(whiteCnt == blackCnt)
{
front = 2;
next = 1;
}
else if(blackCnt == whiteCnt + 1)
{
front = 1;
next = 2;
}
else
{
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))
{
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))
{
//help
board[px1][py1] = front;
if(OneMoveWin(next,px2,py2))
{
printf("Lose in 2 moves.\n");
}
else if(OneMoveWin(front,px2,py2))
{
//help
board[px2][py2] = next;
if(OneMoveWin(front,px3,py3))
{
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
{
printf("Cannot win in 3 moves.\n");
}
}
else
{
printf("Cannot win in 3 moves.\n");
}
}
else
{
if(JudgeSure(front,px1,py1))
{
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
{
printf("Cannot win in 3 moves.\n");
}
}
}
int main()
{
while(scanf("%d",&m)!= EOF,m > 0)
{
Test();
}
return 0;
}posted on 2010-11-11 14:02
bennycen 閱讀(458)
評論(2) 編輯 收藏 引用 所屬分類:
算法題解