http://www.lydsy.com/JudgeOnline/problem.php?id=3106
RunID |
User |
Problem |
Result |
Memory |
Time |
Language |
Code_Length |
Submit_Time |
391578 |
Liu_Ts |
3106 |
Accepted |
96528 kb |
5728 ms |
C++ |
1294 B |
2013-04-16 13:10:46 |
题意
一个n*n(n>=2)棋盘上有黑白棋子各一枚。游戏者A和B轮流移动棋子,A先走。
A:移动白棋子。可以往上下左右四个方向之一移动一格。
B:移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。
当某游戏者把自己的棋子移动到对方棋子所在的格子时就赢了。两个游戏者都很聪明,当可以获胜时会尽快获胜,只能输掉的时候会尽量拖延时间。判断谁会赢,需要多少回合。
题解
不看题解不会- =
然后找到一种很奇怪的做法。。
首先没有平局- =,
如果黑色不在白色的旁边,黑色一定赢(因为白色永远吃不到它0.0)。
接下来的问题是求需要多少步
暴力,然后,其实是卡时。。
我们猜测答案不超过3n步。。。。
记忆化搜索,f[a][b][c][d][x][y]表示白(a,b),黑(c,d),x步,y表示当前游戏者是谁。
于是就过了,不明真相。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=21;
int f[N][N][N][N][N*3][2],n,a,b,c,d;
int DFS(int a,int b,int c,int d,int x,int y)
{
if(x>3*n) return 1<<30;
if(a==c&&b==d) return y==1?1<<30:0;
if(f[a][b][c][d][x][y]) return f[a][b][c][d][x][y];
int &ans=f[a][b][c][d][x][y];
if(y==0)
{
if(a>1) ans=max(ans,DFS(a-1,b,c,d,x+1,1)+1);
if(b>1) ans=max(ans,DFS(a,b-1,c,d,x+1,1)+1);
if(a<n) ans=max(ans,DFS(a+1,b,c,d,x+1,1)+1);
if(b<n) ans=max(ans,DFS(a,b+1,c,d,x+1,1)+1);
}
else
{
ans=1<<30;
if(c>1) ans=min(ans,DFS(a,b,c-1,d,x+1,0)+1);
if(d>1) ans=min(ans,DFS(a,b,c,d-1,x+1,0)+1);
if(c<n) ans=min(ans,DFS(a,b,c+1,d,x+1,0)+1);
if(d<n) ans=min(ans,DFS(a,b,c,d+1,x+1,0)+1);
if(c>2) ans=min(ans,DFS(a,b,c-2,d,x+1,0)+1);
if(d>2) ans=min(ans,DFS(a,b,c,d-2,x+1,0)+1);
if(c+2<=n) ans=min(ans,DFS(a,b,c+2,d,x+1,0)+1);
if(d+2<=n) ans=min(ans,DFS(a,b,c,d+2,x+1,0)+1);
}
return ans;
}
int main()
{
scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
if(abs(a-c)+abs(b-d)==1) printf("WHITE 1\n");
else DFS(a,b,c,d,0,0),printf("BLACK %d\n",f[a][b][c][d][0][0]);
}