Solution - P5380 [THUPC2019]鸭棋

Posted on Edited on

P5380 [THUPC2019]鸭棋

刚打完 P2482 [SDOI2010]猪国杀 来打这道题，感觉超级舒爽。一会儿就打完了。

废话不多说，看详解代码(很多注释)

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

#include<string>
#include<cstdio>
using namespace std;
const int N=10,M=9;
string mp[N][M]={
{"car","horse","elephant","guard","captain","guard","elephant","horse","car"},
{"","","","","","","","",""},
{"duck","","","","","","","","duck"},
{"soldier","","soldier","","soldier","","soldier","","soldier"},
{"","","","","","","","",""},
{"","","","","","","","",""},
{"soldier","","soldier","","soldier","","soldier","","soldier"},
{"duck","","","","","","","","duck"},
{"","","","","","","","",""},
{"car","horse","elephant","guard","captain","guard","elephant","horse","car"}};
string col[N][M]={
{"red","red","red","red","red","red","red","red","red"},
{"","","","","","","","",""},
{"red","","","","","","","","red"},
{"red","","red","","red","","red","","red"},
{"","","","","","","","",""},
{"","","","","","","","",""},
{"blue","","blue","","blue","","blue","","blue"},
{"blue","","","","","","","","blue"},
{"","","","","","","","",""},
{"blue","blue","blue","blue","blue","blue","blue","blue","blue"}};
const int dx_captain[4]={1,0,-1,0},dy_captain[4]={0,1,0,-1},D_captain=4;
const int dx_guard[4]={1,1,-1,-1},dy_guard[4]={1,-1,1,-1},D_guard=4;
const int px_elephant[4]={1,1,-1,-1},py_elephant[4]={1,-1,1,-1};
const int dx_elephant[4]={2,2,-2,-2},dy_elephant[4]={2,-2,2,-2},D_elephant=4;
const int px_horse[8]={1,1,-1,-1,0,0,0,0},py_horse[8]={0,0,0,0,1,1,-1,-1};
const int dx_horse[8]={2,2,-2,-2,1,-1,1,-1},dy_horse[8]={1,-1,1,-1,2,2,-2,-2},D_horse=8;
const int px1_duck[8]={1,1,-1,-1,0,0,0,0},py1_duck[8]={0,0,0,0,1,1,-1,-1};
const int px2_duck[8]={2,2,-2,-2,1,-1,1,-1},py2_duck[8]={1,-1,1,-1,2,2,-2,-2};
const int dx_duck[8]={3,3,-3,-3,2,-2,2,-2},dy_duck[8]={2,-2,2,-2,3,3,-3,-3},D_duck=8;
const int dx_soldier[8]={1,-1,0,0,1,-1,1,-1},dy_soldier[8]={0,0,1,-1,1,-1,-1,1},D_soldier=8;
//以上为打表
//mp表示各个位置的棋子
//col表示各个位置棋子的颜色
//px,py表示各类棋子移动需要满足的前提条件(这些位置必须没有棋子)
//dx,dy表示各类棋子最终能移动到的地方
int Q;//Q组询问
bool GG;//GameOver
string Round="red";//当前轮到哪个玩家
inline void output(int x1,int y1,int x2,int y2);
inline bool inmap(int x,int y){ return x>=0&&x<N&&y>=0&&y<M; }//是否在地图中
inline void put(string s){ for (int i=0;i<s.length();++i)putchar(s[i]); }//输出一个字符串
inline bool pd(int x1,int y1,int x2,int y2,bool jj)
{//判断(x1,y1)的点能不能移动到(x2,y2)
	if (jj&&Round!=col[x1][y1]||GG||col[x1][y1]==col[x2][y2])//jj为1表示是询问时的判断，jj为0表示是判断将军时的判断，第二种情况不需要满足Round.
    //如果游戏结束或不是该轮或颜色相同直接返回false
		return false;
	if (mp[x1][y1]=="captain")//王
	{
		for (int i=0;i<D_captain;++i)
		{
			int nx=x1+dx_captain[i],ny=y1+dy_captain[i];
			if (nx==x2&&ny==y2) return true;
		}
	}
	else if (mp[x1][y1]=="guard")//士
	{
		for (int i=0;i<D_guard;++i)
		{
			int nx=x1+dx_guard[i],ny=y1+dy_guard[i];
			if (nx==x2&&ny==y2) return true;
		}
	}
   //王和士特别简单，只要四个方向试一下就好了
	else if (mp[x1][y1]=="elephant")//象
	{
		for (int i=0;i<D_elephant;++i)
		{
			int nx=x1+px_elephant[i],ny=y1+py_elephant[i];
			if (inmap(nx,ny)&&mp[nx][ny]=="")
			{
				nx=x1+dx_elephant[i],ny=y1+dy_elephant[i];
				if (nx==x2&&ny==y2) return true;
			}
		}
	}
	else if (mp[x1][y1]=="horse")//马
	{
		for (int i=0;i<D_horse;++i)
		{
			int nx=x1+px_horse[i],ny=y1+py_horse[i];
			if (inmap(nx,ny)&&mp[nx][ny]=="")
			{
				nx=x1+dx_horse[i],ny=y1+dy_horse[i];
				if (nx==x2&&ny==y2) return true;
			}
		}
	}
   //象和马比前两个多加了一个判断路径上有没有棋子
	else if (mp[x1][y1]=="car")//车
	{//车很特殊，我采用的是直接模拟
		if (x1==x2)//如果在同一行
		{
			if (y1<y2)//如果在上面
			{
				for (int i=y1+1;inmap(x1,i);++i)
				{//往上走
					if (i==y2) return true;//碰到退出
					if (col[x1][i]!="") return false;
				}//注意这里不能颠倒顺序
			}
			else if (y1>y2)//如果在下面
			{
				for (int i=y1-1;inmap(x1,i);--i)
				{
					if (i==y2) return true;
					if (col[x1][i]!="") return false;
				}
			}
		}
		else if (y1==y2)//如果在同一列
		{
			if (x1<x2)
			{
				for (int i=x1+1;inmap(i,y1);++i)
				{
					if (i==x2) return true;
					if (col[i][y1]!="") return false;
				}
			}
			else if (x1>x2)
			{
				for (int i=x1-1;inmap(i,y1);--i)
				{
					if (i==x2) return true;
					if (col[i][y1]!="") return false;
				}
			}
		}
	}
	else if (mp[x1][y1]=="duck")//鸭
	{//鸭看似复杂，实际上就是马在斜着跳一步，有两个马脚而已 
		for (int i=0;i<D_duck;++i)
		{
			int nx=x1+px1_duck[i],ny=y1+py1_duck[i];//第一个马脚 
			if (inmap(nx,ny)&&col[nx][ny]=="")
			{
				nx=x1+px2_duck[i],ny=y1+py2_duck[i];//第二个马脚 
				if (inmap(nx,ny)&&col[nx][ny]=="")
				{
					nx=x1+dx_duck[i],ny=y1+dy_duck[i];
					if (nx==x2&&ny==y2) return true;//到达 
				}
			}
		}
	}
	else if (mp[x1][y1]=="soldier")//兵 
	{//兵和王和士没有本质区别 
		for (int i=0;i<D_soldier;++i)
		{
			int nx=x1+dx_soldier[i],ny=y1+dy_soldier[i];
			if (nx==x2&&ny==y2) return true;
		}
	}
	return false;
}
inline bool JJ()//判断将军 
{
	for (int i=0;i<N;++i)
		for (int j=0;j<M;++j)
			if (mp[i][j]=="captain")//暴力搜索出王 
				for (int k=0;k<N;++k)
					for (int h=0;h<M;++h)//再暴力枚举每一个点
						if (pd(k,h,i,j,0))//如果可以到达，那就将军了，你也不用管将哪个军 
							return true;
	return false;
}
inline void output(int x1,int y1,int x2,int y2)//可行时输出 
{
	put(col[x1][y1]),putchar(' '),put(mp[x1][y1]),putchar(';');//输出在哪个点 
	if (col[x2][y2]=="") put("NA;");//如果终点没有棋就输出NA 
	else put(col[x2][y2]),putchar(' '),put(mp[x2][y2]),putchar(';');//不然吃掉 
	if (mp[x2][y2]=="captain") GG=1;//如果终点是王即王被吃掉了，那就GG 
	col[x2][y2]=col[x1][y1];
	mp[x2][y2]=mp[x1][y1];
	col[x1][y1]=mp[x1][y1]="";//移动 
	if (JJ()) put("yes;");//[注意]:一定要移动完了再判断将军 
	else put("no;");//判断将军 
	if (GG) put("yes");//判断游戏结束 
	else put("no");
	puts("");
}
inline int read()//快读 
{
	int num=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch<='9'&&ch>='0') num=(num<<1)+(num<<3)+(ch^48),ch=getchar();
	return num;
}
int main()
{
	Q=read();//输入 
	while (Q--)
	{
		int x1=read(),y1=read(),x2=read(),y2=read();
		if (!pd(x1,y1,x2,y2,1)) puts("Invalid command");//如果没办法移动就输出错误 
		else output(x1,y1,x2,y2),Round=Round=="red"?"blue":"red";//要不然就output并转换回合 
	}
}