posts - 33,  comments - 33,  trackbacks - 0
题目链接: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 阅读(426) 评论(2)  编辑 收藏 引用 所属分类: 算法题解

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理