描述：
五子棋是全国智力运动会竞技项目之一，是一种两人对弈的纯策略型棋类游戏。游戏双方分别使用黑白两色的棋子，下在棋盘直线与横线的交叉点上，先在横、竖、斜方向形成五子连线者获胜。 （图） 现有一副五子棋残局存放在 10×10 棋盘中，试判断在某位置下入棋子后，能否获胜。
输入描述：
共十一行。 前十行输入五子棋残局，每行有10个空格间隔的整数。0代表空，1代表黑子，2代表白子。 第十一行有三个逗号间隔的整数i、j、k，表示在棋盘第i行j列下入棋子k。其中i、j∈[1,10]，k∈[1,2]。
输出描述：
一行。 如果该位置已有棋子，输出“Error”；下子后不能获胜输出“No”，能获胜输出“Yes”。
输入样例：
|
1 2 3 4 5 6 7 8 9 10 11 |
1 1 0 1 2 2 2 2 0 0 0 0 1 2 1 1 2 1 1 2 0 0 1 1 2 2 2 2 0 0 0 0 1 1 0 2 1 1 2 0 0 0 2 0 2 1 2 1 0 0 2 2 1 1 2 1 2 1 1 0 0 2 0 1 0 0 2 2 1 0 0 0 0 0 1 1 2 2 0 2 0 0 0 0 1 1 1 2 1 2 0 0 0 0 0 0 0 0 1 2 1,9,2 |
输出样例：
|
1 |
Yes |
二维列表的四个方向遍历
- 先横再竖
|
1 2 3 4 |
for i in range(n): for j in range(m): x, y = i, j pass |
- 先竖再横
|
1 2 3 4 |
for j in range(m): for i in range(n): x, y = i, j pass |
- 对角线
|
1 2 3 4 5 6 |
for i in range(n + m - 1): for j in range(n): x = j y = i - x if (y < 0 or y > m): continue pass |
- 反对角线
|
1 2 3 4 5 6 |
for i in range(n + m - 1): for j in range(n): x = j y = x + m - 1 + i if (y < 0 or y > m): continue pass |
- for example
|
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 |
n = 5 m = 3 for i in range(n): for j in range(m): print(f'({i},{j})', end=' ') print() print() for j in range(m): for i in range(n): print(f'({i},{j})', end=' ') print() print() for i in range(n + m - 1): for j in range(n): x = j y = i - x if (y < 0 or y >= m): continue print(f'({x},{y})', end=' ') print() print() for i in range(n + m - 1): for j in range(n): x = j y = x + m - 1 - i if (y < 0 or y >= m): continue print(f'({x},{y})', end=' ') print() print() |
运行结果:
|
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 |
(0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) (3,0) (3,1) (3,2) (4,0) (4,1) (4,2) **************** (0,0) (1,0) (2,0) (3,0) (4,0) (0,1) (1,1) (2,1) (3,1) (4,1) (0,2) (1,2) (2,2) (3,2) (4,2) **************** (0,0) (0,1) (1,0) (0,2) (1,1) (2,0) (1,2) (2,1) (3,0) (2,2) (3,1) (4,0) (3,2) (4,1) (4,2) **************** (0,2) (0,1) (1,2) (0,0) (1,1) (2,2) (1,0) (2,1) (3,2) (2,0) (3,1) (4,2) (3,0) (4,1) (4,0) |
- 为什么呢。。。
横竖遍历都很容易理解，那对角线要怎么遍历呢？
容易看出第i条对角线经过点(0,m-1-i)和(i,m-1)
所以有：Yi=Xi+m-1-i
容易看出第i条对角线经过点(0,i)和(i,0)
所以有：Yi=i-Xi
用坐标偏移实现八个方向的遍历
注意：当棋盘太大时(n,m>=1e3)时二维列表存不下整个棋盘，就不能用上文的四个方向遍历，而只能字典存有棋子的位置，只能用这种方法了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
move = [ [-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1] ] def find(x, y): res = 0 for (i, j) in move: nx = x ny = y t = 0 while (is_in(nx, ny) and a[nx][ny] == a[x][y]): t += 1 nx += i ny += j res = max(res, t) return res |
发表回复