首页 > 其他 > 详细

BZOJ 3106: [cqoi2013]棋盘游戏

时间:2018-11-08 00:06:59      阅读:187      评论:0      收藏:0      [点我收藏+]
Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 859  Solved: 356
[Submit][Status][Discuss]

Description

一个n*n(n>=2)棋盘上有黑白棋子各一枚。游戏者A和B轮流移动棋子,A先走。
l         A的移动规则:只能移动白棋子。可以往上下左右四个方向之一移动一格。
l         B的移动规则:只能移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。
和通常的“吃子”规则一样,当某游戏者把自己的棋子移动到对方棋子所在的格子时,他就赢了。两个游戏者都很聪明,当可以获胜时会尽快获胜,只能输掉的时候会尽量拖延时间。你的任务是判断谁会赢,需要多少回合。
比如n=2,白棋子在(1,1),黑棋子在(2,2),那么虽然A有两种走法,第二个回合B总能取胜。

Input

输入仅一行,包含五个整数n, r1, c1, r2, c2,即棋盘大小和棋子位置。白色棋子在(r1,c1),黑色棋子在(r2,c2)(1<=r1,c1,r2,c2<=n)。黑白棋子的位置保证不相同。
 

Output

 
输出仅一行,即游戏结果。如果A获胜,输出WHITE x;如果B获胜,输出BLACK x;如果二者都没有必胜策略,输出DRAW。

Sample Input

2 1 1 2 2

Sample Output

BLACK 2

HINT

 

n<=20

题解:暴力DP即可;

f[i][j][k][l][m][n]:表示:第I位,第一,二,三个数用了i,j,k个,n表示是否有进位;

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,a1,a2,b1,b2,ans;
int f[2][70][21][21][21][21];
int work(int x,int step,int c1,int r1,int c2,int r2)
{
	if(step>3*n) return INF;
	int ans;
	if(f[x][step][c1][r1][c2][r2]) return f[x][step][c1][r1][c2][r2];
	if(r1 == r2 && c1 == c2) return x?INF:0;
	if(!x)
	{
		ans=0;
		if(c1>1) ans=max(ans,work(1,step+1,c1-1,r1,c2,r2));
		if(c1<n) ans=max(ans,work(1,step+1,c1+1,r1,c2,r2));
		if(r1>1) ans=max(ans,work(1,step+1,c1,r1-1,c2,r2));
		if(r2<n) ans=max(ans,work(1,step+1,c1,r1+1,c2,r2));
	}
	else
	{
		ans=INF;
		if(r2>1) ans = min(ans, work(0, step+1, c1, r1, c2-1, r2));
        if(r2>2) ans = min(ans, work(0,step+1, c1,r1, c2-2, r2));
        if(r2<n) ans = min(ans, work(0, step+1, c1, r1, c2+1, r2));
        if(r2<n-1) ans = min(ans, work(0, step+1, c1, r1, c2+2, r2));
        if(c2>1) ans = min(ans, work(0, step+1, c1, r1, c2, r2-1));
        if(c2>2) ans = min(ans, work(0, step+1, c1, r1, c2, r2-2));
        if(c2<n) ans = min(ans, work(0, step+1, c1, r1, c2, r2+1));
        if(c2<n-1) ans = min(ans, work(0, step+1, c1, r1, c2, r2+2));
	}

	f[x][step][c1][r1][c2][r2]=++ans;
	return ans;
}
int main()
{
	scanf("%d%d%d%d%d",&n,&a1,&b1,&a2,&b2);
	if(abs(a1-a2)+abs(b1-b2)<=1) printf("WHITE 1\n");
	else printf("BLACK %d\n",work(0,0,a1,b1,a2,b2));
	return 0;
}

  

BZOJ 3106: [cqoi2013]棋盘游戏

原文:https://www.cnblogs.com/songorz/p/9926411.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!