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;
}
/*
4
1 3 3 3
2 3 1 0
3 3 2 0
4 97 64 35
*/