UVALive - 6469（博弈、记忆化搜索）

题意：q,p, r分别代表最底下一行，中间一行和最上面一行的格子数

A、B两人拿格子，每次选中一个格子，则它的上面及右边的格子全部被拿走

谁拿到（1,1）这个格子算输

A先拿，问A是否能赢，若能赢则输出拿的第一个格子的位置

思路：记忆化搜索，如果最后遇到 　r == 0 &&ｐ＝＝０＆＆ｑ＝＝１则说明该情况一定输，那么它的上一种情况一定是赢的

所以枚举ｐ，ｑ，ｒ即可

代码如下：

#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll INF = 1e14 + 7;const int N = 110;int n, m;int dp[N][N][N], col[N][N][N], row[N][N][N];int dfs(int r, int q, int p){	if(r == 0 && q == 0 && p == 1) return dp[r][q][p] = -1;	if(dp[r][q][p]) return dp[r][q][p];	for(int i = r - 1; i >= 0; i--)	{		if(dfs(i, q, p) == -1)		{			col[r][q][p] = i + 1;			row[r][q][p] = 3;			return dp[r][q][p] = 1;		}	}	for(int i = q - 1; i >= 0; i--)	{		if(dfs(min(r, i), i, p) == -1)		{			col[r][q][p] = i + 1;			row[r][q][p] = 2;			return dp[r][q][p] = 1;		}	}	for(int i = p - 1; i >= 1; i--)	{		if(dfs(min(r, i), min(q, i), i) == -1)		{			col[r][q][p] = i + 1;			row[r][q][p] = 1;			return dp[r][q][p] = 1;		}	}	return dp[r][q][p] = -1;}int main(){    int t, cas, p, q, r;    scanf("%d", &t);    memset(dp, 0, sizeof(dp));    while(t--)    {        scanf("%d%d%d%d", &cas, &p, &q, &r);        if(dfs(r, q, p) == -1)        {        	PRintf("%d L/n", cas);        }        else        {        	printf("%d W %d %d/n", cas, col[r][q][p], row[r][q][p]);        }    }    return 0;}/*41 3 3 32 3 1 03 3 2 04 97 64 35*/