牛客多校-Z-Game on grid-(博弈论+必胜态必败态转移)

M

题意：
就是给你一个n×m的棋盘，每个点要么是A，要么是B，要么是 . 。然后机器人刚开始在(1,1)点，Alice先控制机器人走一步,Bob控制机器人走一步。每次只能往右或者下走，不能超过棋盘。如果走到A字母的点，那么Alice就赢了，如果走到B字母的点Bob赢了，如果最后走到字母 . 而且无法移动了，那么就是平局了。现在问：For each test case, output three words ‘yes’ or ‘no’ in one line, representing if Alice can find a way to win, draw or lose the game respectively (without quotes).
翻译下来就是：对于每个样例，输出三个单词(yes,no)，每个单词分别代表，是否Alice可以找到一条路去胜利，平局，输掉，无论Bob怎么影响你。

思考：
1.当时看到这个问法，我就感觉很奇怪，每次的答案也很怪，按平时就直接输出Alice,Bob,draw就是了，但是这次还是3个单词，代表每种答案是否可以。但是当时就感觉很怪，就没多想，害，所以就错在这里了。我以为就是每次尽力让Alice赢就行了，如果她赢了不了就尽力平局，再不行就是输，然后输出就行了。实际上是Alice想要胜利，平局，输掉，是不是都可以。害，一定要好好读题！
2.对于做法，其实只要做出来能不能赢的做法，剩下的两种都一样。对于能不能赢，我就想了，如果直接从(1,1)开始走肯定不行，然后想到博弈题经常用到的就是必胜态和必败态。如果一个点走到的点都是必胜态，那么这个点就是必败态，因为你走过之后把必胜态给别人了。如果一个点走到的点有一个必败态，那么这个点就是必胜态，因为你肯定把这个点走向必败态，把必败态给对手了。黑黑白白，自从做了这题就慢慢的会用必胜态和必败态去推各种点的状态了。
3.但是这个题目还有个不一样的是，必败态和必胜态，是对于Alice和Bob分别来看待的，一个状态要么是Alice的必败，要么是Bob的必败，一个必败态并不是两个人都必败。所以想到这里感觉和平时的不太一样。
4.但是推了推，我感觉就看看走到(i,j)之后，下一步该谁走，如果该Alice走，她肯定走自己的必胜态，如果Bob走，他肯定也走自己的必胜态。如果每个人都走不了必胜，那么就走平局，如果没有平局，那么这个点对他而言是必败态的点。由于每次只能往右边或者下边走，我想处理(i,j)的时候，要保证(i+1,j),(i,j+1)都要处理出来，所以我就想到了从后往前推，先把最后一行处理出来，最后一列处理出来，然后倒着处理就行了，这样每次处理(i,j)的时候，(i+1,j),(i,j+1)都处理出来了。怎么看每个点是谁该走呢？由于每次只能往右和下，那么如果(i+j)%2==0就是该Alice走，否则Bob走。所以每次走的时候，这个点的状态就按自己最好的方向就走就可以了。
5.但是要处理三种情况，一种是Alice想胜利，一种是Alice想平局，一种是Alice想输。既然问无论Bob怎么做，Alice是否都可以。那么就是Alice想到达某种状态的时候，Bob尽量不让他到达就可以了。比如Alice想输，那么Alice就会往Bob的必胜态去走，那么Bob就尽力去往Alice的必胜态走，或者平局走。反正就是反着干。如果处理完后(1,1)的状态是Alice想要的状态，那么这个状态就是yes，否则就是no。

代码：

#include
#define int long long
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;

const int N = 2e5+10,M = 510;

int T,n,m;
char va[M][M];
int vis[M][M];
// 1 win 2 darw 3 lose
bool solve(int op)
{
	for(int i=m;i>=1;i--)
	{
		if(va[n][i]=='B') vis[n][i] = 3;
		if(va[n][i]=='A') vis[n][i] = 1;
		if(va[n][i]=='.')
		{
			if(i+1>m) vis[n][i] = 2;
			else vis[n][i] = vis[n][i+1];
		}
	}
	for(int i=n;i>=1;i--)
	{
		if(va[i][m]=='B') vis[i][m] = 3;
		if(va[i][m]=='A') vis[i][m] = 1;
		if(va[i][m]=='.')
		{
			if(i+1>n) vis[i][m] = 2;
			else vis[i][m] = vis[i+1][m];
		}
	}
	for(int i=n-1;i>=1;i--)
	{
		for(int j=m-1;j>=1;j--)
		{
			if(va[i][j]!='.')
			{
				if(va[i][j]=='A') vis[i][j] = 1;
				if(va[i][j]=='B') vis[i][j] = 3;
				continue;
			}
			int suc1 = 0,suc2 = 0,suc3 = 0;
			if(vis[i+1][j]==1||vis[i][j+1]==1) suc1 = 1;
			if(vis[i+1][j]==2||vis[i][j+1]==2) suc2 = 1;
			if(vis[i+1][j]==3||vis[i][j+1]==3) suc3 = 1;
			if((i+j)%2==0)
			{
				if(op==1)
				{
					if(suc1) vis[i][j] = 1;
					else if(suc2) vis[i][j] = 2;
					else vis[i][j] = 3;
				}
				if(op==2)
				{
					if(suc2) vis[i][j] = 2;
					else if(suc1) vis[i][j] = 1;
					else vis[i][j] = 3;
				}
				if(op==3)
				{
					if(suc3) vis[i][j] = 3;
					else if(suc2) vis[i][j] = 2;
					else vis[i][j] = 1;
				}
			}
			else
			{
				if(op==1)
				{
					if(suc3) vis[i][j] = 3;
					else if(suc2) vis[i][j] = 2;
					else vis[i][j] = 1;
				}
				if(op==2)
				{
					if(suc3) vis[i][j] = 3;
					else if(suc1) vis[i][j] = 1;
					else vis[i][j] = 2;
				}
				if(op==3)
				{
					if(suc1) vis[i][j] = 1;
					else if(suc2) vis[i][j] = 2;
					else vis[i][j] = 3;
				}
			}
		}
	}
	return (vis[1][1]==op);
}

signed main()
{
	IOS;
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			cin>>va[i][j];
		}
		solve(1)?cout<<"yes ":cout<<"no ";
		solve(2)?cout<<"yes ":cout<<"no ";
		solve(3)?cout<<"yes ":cout<<"no ";
		cout<<"\n";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

总结：
仔细读题！多多思考。