萌新求查错
- 板块UVA10838 The Pawn Chess
- 楼主Schwarzkopf_Henkal
- 当前回复2
- 已保存回复2
- 发布时间2020/7/13 18:57
- 上次更新2023/11/6 23:11:23
查看原帖
被骇客银狼阻止的越权访问保存失败
萌新求查错
样例过了，Udebug上面的数据也过了，但是WA了，感觉没问题？不会Alpha-Beta剪枝，所以只打了个记忆化。
题意：有一个4x4的棋盘，上面有黑色（用'p'表示）和白色（用'P'表示）两种棋子，白先手，对于白的每个棋子可以向上走一步或斜向上吃掉一个黑色棋子，黑色棋子则相反，当有白色棋子在最上面那一行，或者所有的黑色棋子都被吃掉了，或者所有的黑色棋子没有合法的移动的时候，白色胜利，黑白双方都会最优地下棋，如果自己会输会拖延尽量长的时间，如果自己会赢则会尽快胜利，输出最后的赢家和他需要的步数。注意，如果白胜利，答案将一直是偶数，如果黑胜利，答案将一直是奇数。
状态的定义：在当前布局，turn先手的情况下，如果能取得胜利，最少的步数（奇数）如果不能取得胜利，最大的拖延时间（偶数）
思路是，对于一个状态，如果儿子里有奇数的，那么选奇数，因为偶数则代表会失败如果有奇数，那就奇数里取min，否则偶数里取max。
代码：剪贴板
#include<bits/stdc++.h>
using namespace std;
int T,s[6][6];
char c[6][6];
typedef unsigned long long ull;
typedef long long ll;
map<ull,ll>mmp;
struct node{
int x[6][6];
};
long long dfs(node x,bool turn){//0=white 1=black
int cntw=0,cntb=0,fw=0,fb=0,vict=0;//分别对应有无？能否走？是否到达对面？
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++){
if(x.x[i][j]==1){
if(i==4)
vict=1;
cntb++;
if(x.x[i+1][j]==0||x.x[i+1][j-1]==2||x.x[i+1][j+1]==2)
fb=1;
}
if(x.x[i][j]==2){
if(i==1)
vict=2;
cntw++;
if(x.x[i-1][j]==0||x.x[i-1][j-1]==1||x.x[i-1][j+1]==1)
fw=1;
}
}
if(vict||cntw==0||cntb==0||fw==0||fb==0){
return 0;
}
long long res=1e9;
int y[6][6];//注意只要是偶数就是黑赢。
if(turn){//Black (lives matter)
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++){
if(x.x[i][j]==1){
if(x.x[i+1][j]==0){
memcpy(y,x.x,sizeof(x.x));
y[i+1][j]=1;
y[i][j]=0;
ull ash=0;
for(int k=1;k<=4;k++)
for(int l=1;l<=4;l++)
ash=ash*3+y[k][l];
ash=ash*3+!turn;
node doge;
memcpy(doge.x,y,sizeof(y));
long long cur;
if(mmp.count(ash))
cur=mmp[ash]+1;
else cur=mmp[ash]=dfs(doge,!turn)+1;
if(res==1e9)
res=cur;
else {
if(cur%2){
if(res%2)
res=min(res,cur);
else res=cur;
}else if(res%2==0){
res=max(res,cur);
}
}
}
if(x.x[i+1][j-1]==2){
memcpy(y,x.x,sizeof(x.x));
y[i+1][j-1]=1;
y[i][j]=0;
ull ash=0;
for(int k=1;k<=4;k++)
for(int l=1;l<=4;l++)
ash=ash*3+y[k][l];
ash=ash*3+!turn;
node doge;
memcpy(doge.x,y,sizeof(y));
long long cur;
if(mmp.count(ash))
cur=mmp[ash]+1;
else cur=mmp[ash]=dfs(doge,!turn)+1;
if(res==1e9)
res=cur;
else {
if(cur%2){
if(res%2)
res=min(res,cur);
else res=cur;
}else if(res%2==0){
res=max(res,cur);
}
}
}
if(x.x[i+1][j+1]==2){
memcpy(y,x.x,sizeof(x.x));
y[i+1][j+1]=1;
y[i][j]=0;
ull ash=0;
for(int k=1;k<=4;k++)
for(int l=1;l<=4;l++)
ash=ash*3+y[k][l];
ash=ash*3+!turn;
node doge;
memcpy(doge.x,y,sizeof(y));
long long cur;
if(mmp.count(ash))
cur=mmp[ash]+1;
else cur=mmp[ash]=dfs(doge,!turn)+1;
if(res==1e9)
res=cur;
else {
if(cur%2){
if(res%2)
res=min(res,cur);
else res=cur;
}else if(res%2==0){
res=max(res,cur);
}
}
}
}
}
// for(int i=1;i<=4;i++){
// for(int j=1;j<=4;j++)
// cout<<x.x[i][j]<<" ";
// cout<<'\n';
// }
// cout<<"Black"<<res<<endl<<endl;
return res;
}else {//white
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++){
if(x.x[i][j]==2){
if(x.x[i-1][j]==0){
memcpy(y,x.x,sizeof(x.x));
y[i-1][j]=2;
y[i][j]=0;
ull ash=0;
for(int k=1;k<=4;k++)
for(int l=1;l<=4;l++)
ash=ash*3+y[k][l];
ash=ash*3+!turn;
node doge;
memcpy(doge.x,y,sizeof(y));
long long cur;
if(mmp.count(ash))
cur=mmp[ash]+1;
else cur=mmp[ash]=dfs(doge,!turn)+1;
if(res==1e9)
res=cur;
else {
if(cur%2){
if(res%2)
res=min(res,cur);
else res=cur;
}else if(res%2==0){
res=max(res,cur);
}
}
}
if(x.x[i-1][j-1]==1){
memcpy(y,x.x,sizeof(x.x));
y[i-1][j-1]=2;
y[i][j]=0;
ull ash=0;
for(int k=1;k<=4;k++)
for(int l=1;l<=4;l++)
ash=ash*3+y[k][l];
ash=ash*3+!turn;
node doge;
memcpy(doge.x,y,sizeof(y));
long long cur;
if(mmp.count(ash))
cur=mmp[ash]+1;
else cur=mmp[ash]=dfs(doge,!turn)+1;
if(res==1e9)
res=cur;
else {
if(cur%2){
if(res%2)
res=min(res,cur);
else res=cur;
}else if(res%2==0){
res=max(res,cur);
}
}
}
if(x.x[i-1][j+1]==1){
memcpy(y,x.x,sizeof(x.x));
y[i-1][j+1]=2;
y[i][j]=0;
ull ash=0;
for(int k=1;k<=4;k++)
for(int l=1;l<=4;l++)
ash=ash*3+y[k][l];
ash=ash*3+!turn;
node doge;
memcpy(doge.x,y,sizeof(y));
long long cur;
if(mmp.count(ash))
cur=mmp[ash]+1;
else cur=mmp[ash]=dfs(doge,!turn)+1;
if(res==1e9)
res=cur;
else {
if(cur%2){
if(res%2)
res=min(res,cur);
else res=cur;
}else if(res%2==0){
res=max(res,cur);
}
}
}
}
}
// for(int i=1;i<=4;i++){
// for(int j=1;j<=4;j++)
// cout<<x.x[i][j]<<" ";
// cout<<'\n';
// }
// cout<<"White"<<res<<endl<<endl;
return res;
}
}//状态应该是当前拜访当前先手胜者最少？
int main(){
// freopen("Udebug.out","w",stdout);
cin>>T;
while(T--){
memset(s,0,sizeof(s));
mmp.clear();
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++){
cin>>c[i][j];
if(c[i][j]=='p')//p=black=1
s[i][j]=1;
if(c[i][j]=='P')//P=white=2
s[i][j]=2;
}
node doge;
memcpy(doge.x,s,sizeof(s));
ll ans=dfs(doge,0);
if(ans%2)
cout<<"white ("<<ans<<")";
else cout<<"black ("<<ans<<")";
if(T)
cout<<'\n';
}
}
加载中...