fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<queue>
  4. using namespace std;
  5. struct wolf{
  6. 	int depth;
  7. 	int r[4];
  8. 	int c[4];
  9. 	wolf(){}
  10. 	wolf(int a,int b,int C,int d,int e,int f,int g,int h,int D){
  11. 		r[0]=a;
  12. 		c[0]=b;
  13. 		r[1]=C;
  14. 		c[1]=d;
  15. 		r[2]=e;
  16. 		c[2]=f;
  17. 		r[3]=g;
  18. 		c[3]=h;
  19. 		depth=D;
  20. 	}
  21. };
  22. bool bfs[8][8][8][8][8][8][8][8];
  23. pair<int,int> p[4];
  24. int main(){
  25. 	int a,b,c,d,e,f,g,h;
  26. 	scanf("%d%d%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f,&g,&h);
  27. 	a--;
  28. 	b--;
  29. 	c--;
  30. 	d--;
  31. 	e--;
  32. 	f--;
  33. 	g--;
  34. 	h--;
  35. 	p[0]=make_pair(a,b);
  36. 	p[1]=make_pair(c,d);
  37. 	p[2]=make_pair(e,f);
  38. 	p[3]=make_pair(g,h);
  39. 	std::sort(p,p+4);
  40. 	queue<wolf>Q;
  41. 	Q.push(wolf(p[3].first,p[3].second,p[2].first,p[2].second,p[1].first,p[1].second,p[0].first,p[0].second,0));
  42. 	scanf("%d%d%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f,&g,&h);
  43. 	a--;
  44. 	b--;
  45. 	c--;
  46. 	d--;
  47. 	e--;
  48. 	f--;
  49. 	g--;
  50. 	h--;
  51. 	p[0]=make_pair(a,b);
  52. 	p[1]=make_pair(c,d);
  53. 	p[2]=make_pair(e,f);
  54. 	p[3]=make_pair(g,h);
  55. 	std::sort(p,p+4);
  56. 	while(Q.size()){
  57. 		wolf at=Q.front();
  58. 		Q.pop();
  59. 		if(at.r[0]<at.r[1]||(at.r[0]==at.r[1]&&at.c[0]<at.c[1])){
  60. 			int m=at.r[0];
  61. 			int n=at.c[0];
  62. 			at.r[0]=at.r[1];
  63. 			at.r[1]=m;
  64. 			at.c[0]=at.c[1];
  65. 			at.c[1]=n;
  66. 		}
  67. 		if(at.r[0]<at.r[2]||(at.r[0]==at.r[2]&&at.c[0]<at.c[2])){
  68. 			int m=at.r[0];
  69. 			int n=at.c[0];
  70. 			at.r[0]=at.r[2];
  71. 			at.r[2]=m;
  72. 			at.c[0]=at.c[2];
  73. 			at.c[2]=n;
  74. 		}
  75. 		if(at.r[0]<at.r[3]||(at.r[0]==at.r[3]&&at.c[0]<at.c[3])){
  76. 			int m=at.r[0];
  77. 			int n=at.c[0];
  78. 			at.r[0]=at.r[3];
  79. 			at.r[3]=m;
  80. 			at.c[0]=at.c[3];
  81. 			at.c[3]=n;
  82. 		}
  83. 		if(at.r[1]<at.r[2]||(at.r[1]==at.r[2]&&at.c[1]<at.c[2])){
  84. 			int m=at.r[1];
  85. 			int n=at.c[1];
  86. 			at.r[1]=at.r[2];
  87. 			at.r[2]=m;
  88. 			at.c[1]=at.c[2];
  89. 			at.c[2]=n;
  90. 		}
  91. 		if(at.r[1]<at.r[3]||(at.r[1]==at.r[3]&&at.c[1]<at.c[3])){
  92. 			int m=at.r[1];
  93. 			int n=at.c[1];
  94. 			at.r[1]=at.r[3];
  95. 			at.r[3]=m;
  96. 			at.c[1]=at.c[3];
  97. 			at.c[3]=n;
  98. 		}
  99. 		if(at.r[2]<at.r[3]||(at.r[2]==at.r[3]&&at.c[2]<at.c[3])){
  100. 			int m=at.r[2];
  101. 			int n=at.c[2];
  102. 			at.r[2]=at.r[3];
  103. 			at.r[3]=m;
  104. 			at.c[2]=at.c[3];
  105. 			at.c[3]=n;
  106. 		}
  107. 		int O=at.depth+1;
  108. 		if(bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]])continue;
  109. 		bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]=true;
  110. 		if(at.depth==8)continue;
  111. 	//	if(at.r[0]==3&&at.c[0]==5&&at.c[1]==5&&at.c[2]==2)printf("%d %d %d %d %d %d %d %d\n",at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3]);
  112. 		bool k;
  113. 		bool z;
  114. 		k=false;
  115. 		z=false;
  116. 		for(int j=0;j<4;j++){
  117. 			if(at.r[j]==at.r[0]-1&&at.c[j]==at.c[0])k=true;
  118. 			if(at.r[j]==at.r[0]-2&&at.c[j]==at.c[0])z=true;
  119. 		}
  120. 		if(!z&&k&&at.r[0]>=2&&!bfs[at.r[0]-2][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  121. 			Q.push(wolf(at.r[0]-2,at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  122. 		}else if(!k&&at.r[0]>=1&&!bfs[at.r[0]-1][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  123. 			Q.push(wolf(at.r[0]-1,at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  124. 		}
  125. 		k=false;
  126. 		z=false;
  127. 		for(int j=0;j<4;j++){
  128. 			if(at.r[j]==at.r[0]+1&&at.c[j]==at.c[0])k=true;
  129. 			if(at.r[j]==at.r[0]+2&&at.c[j]==at.c[0])z=true;
  130. 		}
  131. 		if(!z&&k&&at.r[0]<6&&!bfs[at.r[0]+2][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  132. 			Q.push(wolf(at.r[0]+2,at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  133. 		}else if(!k&&at.r[0]<7&&!bfs[at.r[0]+1][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  134. 			Q.push(wolf(at.r[0]+1,at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  135. 		}
  136. 		k=false;
  137. 		z=false;
  138. 		for(int j=0;j<4;j++){
  139. 			if(at.c[j]==at.c[0]-1&&at.r[j]==at.r[0])k=true;
  140. 			if(at.c[j]==at.c[0]-2&&at.r[j]==at.r[0])z=true;
  141. 		}
  142. 		if(!z&&k&&at.c[0]>=2&&!bfs[at.r[0]][at.c[0]-2][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  143. 			Q.push(wolf(at.r[0],at.c[0]-2,at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  144. 		}else if(!k&&at.c[0]>=1&&!bfs[at.r[0]][at.c[0]-1][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  145. 			Q.push(wolf(at.r[0],at.c[0]-1,at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  146. 		}
  147. 		k=false;
  148. 		z=false;
  149. 		for(int j=0;j<4;j++){
  150. 			if(at.c[j]==at.c[0]+1&&at.r[j]==at.r[0])k=true;
  151. 			if(at.c[j]==at.c[0]+2&&at.r[j]==at.r[0])z=true;
  152. 		}
  153. 		if(!z&&k&&at.c[0]<6&&!bfs[at.r[0]][at.c[0]+2][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  154. 			Q.push(wolf(at.r[0],at.c[0]+2,at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  155. 		}else if(!k&&at.c[0]<7&&!bfs[at.r[0]][at.c[0]+1][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  156. 			Q.push(wolf(at.r[0],at.c[0]+1,at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  157. 		}
  158.  
  159. 		k=false;
  160. 		z=false;
  161. 		for(int j=0;j<4;j++){
  162. 			if(at.r[j]==at.r[1]-1&&at.c[j]==at.c[1])k=true;
  163. 			if(at.r[j]==at.r[1]-2&&at.c[j]==at.c[1])z=true;
  164. 		}
  165. 		if(!z&&k&&at.r[1]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]-2][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  166. 			Q.push(wolf(at.r[0],at.c[0],at.r[1]-2,at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  167. 		}else if(!k&&at.r[1]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]-1][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  168. 			Q.push(wolf(at.r[0],at.c[0],at.r[1]-1,at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  169. 		}
  170. 		k=false;
  171. 		z=false;
  172. 		for(int j=0;j<4;j++){
  173. 			if(at.r[j]==at.r[1]+1&&at.c[j]==at.c[1])k=true;
  174. 			if(at.r[j]==at.r[1]+2&&at.c[j]==at.c[1])z=true;
  175. 		}
  176. 		if(!z&&k&&at.r[1]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]+2][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  177. 			Q.push(wolf(at.r[0],at.c[0],at.r[1]+2,at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  178. 		}else if(!k&&at.r[1]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]+1][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  179. 			Q.push(wolf(at.r[0],at.c[0],at.r[1]+1,at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
  180. 		}
  181. 		k=false;
  182. 		z=false;
  183. 		for(int j=0;j<4;j++){
  184. 			if(at.c[j]==at.c[1]-1&&at.r[j]==at.r[1])k=true;
  185. 			if(at.c[j]==at.c[1]-2&&at.r[j]==at.r[1])z=true;
  186. 		}
  187. 		if(!z&&k&&at.c[1]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]-2][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  188. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1]-2,at.r[2],at.c[2],at.r[3],at.c[3],O));
  189. 		}else if(!k&&at.c[1]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]-1][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  190. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1]-1,at.r[2],at.c[2],at.r[3],at.c[3],O));
  191. 		}
  192. 		k=false;
  193. 		z=false;
  194. 		for(int j=0;j<4;j++){
  195. 			if(at.c[j]==at.c[1]+1&&at.r[j]==at.r[1])k=true;
  196. 			if(at.c[j]==at.c[1]+2&&at.r[j]==at.r[1])z=true;
  197. 		}
  198. 		if(!z&&k&&at.c[1]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]+2][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  199. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1]+2,at.r[2],at.c[2],at.r[3],at.c[3],O));
  200. 		}else if(!k&&at.c[1]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]+1][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
  201. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1]+1,at.r[2],at.c[2],at.r[3],at.c[3],O));
  202. 		}
  203.  
  204. 		k=false;
  205. 		z=false;
  206. 		for(int j=0;j<4;j++){
  207. 			if(at.r[j]==at.r[2]-1&&at.c[j]==at.c[2])k=true;
  208. 			if(at.r[j]==at.r[2]-2&&at.c[j]==at.c[2])z=true;
  209. 		}
  210. 		if(!z&&k&&at.r[2]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]-2][at.c[2]][at.r[3]][at.c[3]]){
  211. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2]-2,at.c[2],at.r[3],at.c[3],O));
  212. 		}else if(!k&&at.r[2]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]-1][at.c[2]][at.r[3]][at.c[3]]){
  213. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2]-1,at.c[2],at.r[3],at.c[3],O));
  214. 		}
  215. 		k=false;
  216. 		z=false;
  217. 		for(int j=0;j<4;j++){
  218. 			if(at.r[j]==at.r[2]+1&&at.c[j]==at.c[2])k=true;
  219. 			if(at.r[j]==at.r[2]+2&&at.c[j]==at.c[2])z=true;
  220. 		}
  221. 		if(!z&&k&&at.r[2]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]+2][at.c[2]][at.r[3]][at.c[3]]){
  222. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2]+2,at.c[2],at.r[3],at.c[3],O));
  223. 		}else if(!k&&at.r[2]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]+1][at.c[2]][at.r[3]][at.c[3]]){
  224. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2]+1,at.c[2],at.r[3],at.c[3],O));
  225. 		}
  226. 		k=false;
  227. 		z=false;
  228. 		for(int j=0;j<4;j++){
  229. 			if(at.c[j]==at.c[2]-1&&at.r[j]==at.r[2])k=true;
  230. 			if(at.c[j]==at.c[2]-2&&at.r[j]==at.r[2])z=true;
  231. 		}
  232. 		if(!z&&k&&at.c[2]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]-2][at.r[3]][at.c[3]]){
  233. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2]-2,at.r[3],at.c[3],O));
  234. 		}else if(!k&&at.c[2]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]-1][at.r[3]][at.c[3]]){
  235. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2]-1,at.r[3],at.c[3],O));
  236. 		}
  237. 		k=false;
  238. 		z=false;
  239. 		for(int j=0;j<4;j++){
  240. 			if(at.c[j]==at.c[2]+1&&at.r[j]==at.r[2])k=true;
  241. 			if(at.c[j]==at.c[2]+2&&at.r[j]==at.r[2])z=true;
  242. 		}
  243. 		if(!z&&k&&at.c[2]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]+2][at.r[3]][at.c[3]]){
  244. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2]+2,at.r[3],at.c[3],O));
  245. 		}else if(!k&&at.c[2]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]+1][at.r[3]][at.c[3]]){
  246. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2]+1,at.r[3],at.c[3],O));
  247. 		}
  248.  
  249. 		k=false;
  250. 		z=false;
  251. 		for(int j=0;j<4;j++){
  252. 			if(at.r[j]==at.r[3]-1&&at.c[j]==at.c[3])k=true;
  253. 			if(at.r[j]==at.r[3]-2&&at.c[j]==at.c[3])z=true;
  254. 		}
  255. 		if(!z&&k&&at.r[3]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]-2][at.c[3]]){
  256. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3]-2,at.c[3],O));
  257. 		}else if(!k&&at.r[3]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]-1][at.c[3]]){
  258. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3]-1,at.c[3],O));
  259. 		}
  260. 		k=false;
  261. 		z=false;
  262. 		for(int j=0;j<4;j++){
  263. 			if(at.r[j]==at.r[3]+1&&at.c[j]==at.c[3])k=true;
  264. 			if(at.r[j]==at.r[3]+2&&at.c[j]==at.c[3])z=true;
  265. 		}
  266. 		if(!z&&k&&at.r[3]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]+2][at.c[3]]){
  267. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3]+2,at.c[3],O));
  268. 		}else if(!k&&at.r[3]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]+1][at.c[3]]){
  269. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3]+1,at.c[3],O));
  270. 		}
  271. 		k=false;
  272. 		z=false;
  273. 		for(int j=0;j<4;j++){
  274. 			if(at.c[j]==at.c[3]-1&&at.r[j]==at.r[3])k=true;
  275. 			if(at.c[j]==at.c[3]-2&&at.r[j]==at.r[3])z=true;
  276. 		}
  277. 		if(!z&&k&&at.c[3]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]-2]){
  278. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3]-2,O));
  279. 		}else if(!k&&at.c[3]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]-1]){
  280. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3]-1,O));
  281. 		}
  282. 		k=false;
  283. 		z=false;
  284. 		for(int j=0;j<4;j++){
  285. 			if(at.c[j]==at.c[3]+1&&at.r[j]==at.r[3])k=true;
  286. 			if(at.c[j]==at.c[3]+2&&at.r[j]==at.r[3])k=true;
  287. 		}
  288. 		if(!z&&k&&at.c[3]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]+2]){
  289. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3]+2,O));
  290. 		}else if(!k&&at.c[3]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]+1]){
  291. 			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3]+1,O));
  292. 		}
  293. 		if(bfs[p[3].first][p[3].second][p[2].first][p[2].second][p[1].first][p[1].second][p[0].first][p[0].second])break;
  294. 	}
  295. 	if(bfs[p[3].first][p[3].second][p[2].first][p[2].second][p[1].first][p[1].second][p[0].first][p[0].second])printf("YES\n");
  296. 	else printf("NO\n");
  297. }
Runtime error #stdin #stdout 0s 19872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FwkA7F
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!