题意：给一个只有三行的方阵。然后再给一个100>=p>=q>=r>=0分别代表最底部的方块数，中部的方块数，顶部的方块数。
它有以下规则：
输者：取到左下角方块的人，或者这个人面临的情况没有方块可取。
赢者：只要对手输，你就赢了。
取方块的规则为：
选定一个方块，把这个方块，以及它上面的，和它右边的，所有方块取走。
也就是说，取一个方块，把它以及它包括右上边的方块全部取走。
问题：如果先走的人能赢，它应该先取哪个方块(行从下往上标号，列从左往右标号)
如果能赢，就输出W 列 行
否则输出L
记忆化搜索
首先面临1 0 0的这种情况肯定是会输的。
所以ha[1][0][0]=0
然后，如果能多走一步，走完后面临这种情况的人一定输，走那一步的人一定赢
然后直接dfs就行。
首先从最底行开始，假设选择最底行的最后一个方块，倒数第二个方块，直到等于第二个方块为止。
同理第二行，第三行。
这题其实说起来一文不值= =
可恨我当初连题目都没读懂。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 101
int ha[MAXN][MAXN][MAXN];
int row,col;
bool dfs(int p,int q,int r){
if(ha[p][q][r]==1)return 1;
else if(ha[p][q][r]==0)return 0;
else{
int p1,q1,r1;
for(p1=p;p1>=2;p1--){
q1=min(p1-1,q);
r1=min(q1,r);
if(dfs(p1-1,q1,r1)==0){
row=1;col=p1;
return ha[p][q][r]=1;
}
}
for(q1=q;q1>=1;q1--){
r1=min(r,q1-1);
if(dfs(p,q1-1,r1)==0){
row=2;col=q1;
return ha[p][q][r]=1;
}
}
for(r1=r;r1>=1;r1--){
if(dfs(p,q,r1-1)==0){
row=3;col=r1;
return ha[p][q][r]=1;
}
}
return ha[p][q][r]=0;
}
}
int main()
{
int t;
scanf("%d",&t);
memset(ha,-1,sizeof(ha));
ha[1][0][0]=0;
while(t--){
int p,q,r,cas;
scanf("%d%d%d%d",&cas,&p,&q,&r);
ha[p][q][r]=-1;
if(dfs(p,q,r)==0){
printf("%d L\n",cas);
}
else {
printf("%d W %d %d\n",cas,col,row);
}
}
return 0;
}
|
