B. Five-In-a-Row

Codeforces
IDCF825B
Time1000ms
Memory256MB
Difficulty
brute forceimplementation
English · Original
Chinese · Translation
Formal · Original
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'_. [samples]
Alice 和 Bob 玩五子棋游戏。他们有一个 $10\times 10$ 的棋盘。两人轮流放置十字(×)或圆圈(○),每次放一个。Alice 放十字,Bob 放圆圈。 在当前对局中,双方已经进行了一些回合,现在轮到 Alice 行动。她想知道是否能在某个空格中放置一个十字,从而立即获胜。 Alice 获胜的条件是:棋盘上存在一条由十字组成的直线,长度 *不小于 5*。这条直线可以是水平、垂直或对角线方向的。 给你一个 $10\times 10$ 的矩阵(共 10 行,每行 10 个字符),其中大写拉丁字母 _'X'_ 表示十字,字母 _'O'_ 表示圆圈,_'.'_ 表示空格。十字的数量等于圆圈的数量,且每种符号至少有一个。至少存在一个空格。 保证当前局面下,没有人已经获胜。 如果 Alice 能通过在某个空格中放置一个十字立即获胜,请输出 _'YES'_;否则输出 _'NO'_。 ## Input 给你一个 $10\times 10$ 的矩阵(共 10 行,每行 10 个字符),其中大写拉丁字母 _'X'_ 表示十字,字母 _'O'_ 表示圆圈,_'.'_ 表示空格。十字的数量等于圆圈的数量,且每种符号至少有一个。至少存在一个空格。保证当前局面下,没有人已经获胜。 ## Output 如果 Alice 能通过在某个空格中放置一个十字立即获胜,请输出 _'YES'_;否则输出 _'NO'_。 [samples]
**Definitions** Let $ M \in \{ \text{'X'}, \text{'O'}, \text{'.'} \}^{10 \times 10} $ be a 10×10 matrix representing the game board, where: - $\text{'X'}$ denotes Alice's cross, - $\text{'O'}$ denotes Bob's nought, - $\text{'.'}$ denotes an empty cell. Let $ E = \{ (i, j) \in \{0, \dots, 9\}^2 \mid M[i][j] = \text{'.'} \} $ be the set of empty cells. **Constraints** 1. $ | \{ (i,j) \mid M[i][j] = \text{'X'} \} | = | \{ (i,j) \mid M[i][j] = \text{'O'} \} | $ 2. $ | \{ (i,j) \mid M[i][j] = \text{'X'} \} | \geq 1 $, $ | \{ (i,j) \mid M[i][j] = \text{'O'} \} | \geq 1 $, $ |E| \geq 1 $ 3. No line of 5 or more consecutive 'X' or 'O' exists in any of the 8 directions (horizontal, vertical, diagonal) in the current state. **Objective** Determine whether there exists a cell $ (i, j) \in E $ such that, if $ M[i][j] $ is changed from '.' to 'X', there exists a line (contiguous sequence) of at least 5 consecutive 'X' in any of the four directions: - Horizontal: same row, consecutive columns, - Vertical: same column, consecutive rows, - Diagonal (main): $ (i+k, j+k) $ for $ k \in \mathbb{Z} $, - Diagonal (anti): $ (i+k, j-k) $ for $ k \in \mathbb{Z} $. Output "YES" if such a cell exists; otherwise output "NO".
Samples
Input #1
XX.XX.....
.....OOOO.
..........
..........
..........
..........
..........
..........
..........
..........
Output #1
YES
Input #2
XXOXX.....
OO.O......
..........
..........
..........
..........
..........
..........
..........
..........
Output #2
NO
API Response (JSON)
{
  "problem": {
    "name": "B. Five-In-a-Row",
    "description": {
      "content": "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 th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF825B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\n\nIn current match th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Alice 和 Bob 玩五子棋游戏。他们有一个 $10\\times 10$ 的棋盘。两人轮流放置十字(×)或圆圈(○),每次放一个。Alice 放十字,Bob 放圆圈。\n\n在当前对局中,双方已经进行了一些回合,现在轮到 Alice 行动。她想知道是否能在某个空格中放置一个十字,从而立即获胜。\n\nAlice 获胜的条件是:棋盘上存在一条由十字组成的直线,长度 *不小于 5*。这条直线可以是水平、垂...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ M \\in \\{ \\text{'X'}, \\text{'O'}, \\text{'.'} \\}^{10 \\times 10} $ be a 10×10 matrix representing the game board, where:  \n- $\\text{'X'}$ denotes Alice's cross,  \n- $\\text{'O'}$ d...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments