【CodeForces-825B】解题报告（模拟，五子棋）

原始题目

B. Five-In-a-Row

  • time limit per test 1 second

  • memory limit per test 256 megabytes

  • input standard input

  • output standard output

Alice and Bob play 5-in-a-row game. They have a playing field of size 10 × 10. In turns they put either crosses or noughts, one at a time. Alice puts crosses and Bob puts noughts.

In current match they have made some turns and now it's Alice's turn. She wonders if she can put cross in such empty cell that she wins immediately.

Alice wins if some crosses in the field form line of length not smaller than 5. This line can be horizontal, vertical and diagonal.

Input

You are given matrix 10 × 10 (10 lines of 10 characters each) with capital Latin letters 'X' being a cross, letters 'O' being a nought and '.' being an empty cell. The number of 'X' cells is equal to the number of 'O' cells and there is at least one of each type. There is at least one empty cell.

It is guaranteed that in the current arrangement nobody has still won.

Output

Print 'YES' if it's possible for Alice to win in one turn by putting cross in some empty cell. Otherwise print 'NO'.

Examples

input

XX.XX.....
.....OOOO.
..........
..........
..........
..........
..........
..........
..........
..........

output

YES

input

XXOXX.....
OO.O......
..........
..........
..........
..........
..........
..........
..........
..........

output

NO

题目大意

给定一个五子棋棋盘，判断X棋一步之后能否胜利。

解题思路

没什么，自己写模拟。遍历每个可下的点判断横竖和斜方向上能否实现大于等于五子相连。

注意边界问题，可以采用左右上下各拓展4行4列。

解题代码

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

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define maxn 10010
using namespace std;
char map[20][20];
bool check(int a,int b)
{
	map[a][b]=1;
//	printf("begin check %d %d\n",a,b);
		int conti,i,j;
		for(conti=0,i=a-4;i<=a+4;i++) //横向判断 
		{
			if(map[i][b]==1) 
			{
				conti++;
				if(conti>4) return true;
			}
			else
			{
				conti=0;
				continue;
			}
		} 
		for(conti=0,j=b-4;j<=b+4;j++) //纵向判断 
		{
			if(map[a][j]==1) 
			{
				conti++;
				if(conti>4) return true;
			}
			else
			{
				conti=0;
				continue;
			}
		} 
		for(conti=0,i=a-4,j=b-4;i<=a+4;i++,j++) //斜向判断1 
		{
			if(map[i][j]==1)
			{
				conti++;
				if(conti>4) return true;
			}
			else 
			{
				conti=0;
				continue;
			}
		}
		
		for(conti=0,i=a-4,j=b+4;i<=a+4;i++,j--) //斜向判断1 
		{
			if(map[i][j]==1)
			{
				conti++;
				if(conti>4) return true;
			}
			else 
			{
				conti=0;
				continue;
			}
		}
		map[a][b]=0;
		return false; 
}
int main()
{
//	freopen("in.txt", "r", stdin);//其实in.txt是可以修改成其他名字的  比如“输入.txt”，都是可以的，这里只是为了方便起见，下同； 
	for(int i=0+4;i<10+4;i++)
	{
		scanf("%s",map[i]+4);	
	}
	for(int i=0+4;i<10+4;i++)
	{
		for(int j=0+4;j<10+4;j++)
		{
			switch(map[i][j])	
			{
				case 'X': map[i][j]=1;break;
				case 'O': map[i][j]=2;break;
				case '.': map[i][j]=0;break;
			}
//			printf("%d ",map[i][j]);
		}
//		printf("\n");
	}
	int flag=0;
	for(int i=0+4;i<10+4;i++)
	{
		for(int j=0+4;j<10+4;j++)
		{
			if(map[i][j]||!map[i-1][j]&&!map[i+1][j]&&!map[i][j-1]&&!map[i][j+1]&&!map[i-1][j-1]&&!map[i+1][j+1]&&!map[i-1][j+1]&&!map[i+1][j-1]) continue;
			else flag=check(i,j);
			if(flag)
			{
//				printf("%d %d \n",i-4,j-4);
				break;
			}
		}
		if(flag)
			break;
	}
	if(flag)
		printf("YES\n");
	else printf("NO\n");
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

总结与反思

模拟的时候要注意细节，尽量不要返工。

能简化的简化（后面会学到剪纸），比如判定周围一圈没有棋子可以直接continue跳过该循环。