[CCC 2023 J5] CCC Word Hunt

Luogu

IDLGP9303

Time3000ms

Memory512MB

DifficultyP3

2023CCC（加拿大）

In the CCC Word Hunt, words are hidden in a grid of letters. The letters of a hidden word always appear in order on horizontal, vertical, or diagonal line segments in one of two ways.One way is for the letters of a word to appear on one line segment. The other way is for the letters of a word to appear on one line segment up to some letter and then on a second line segment that forms a right angle at this letter. Given a grid of letters and a single word to search for, your job is to determine the number of times that particular word is hidden in the grid. ## Input The first line of input will contain a string of distinct uppercase letters $W$,representing the word you are to search for in the grid. The length of $W$ will be at least two. The second line of input will be an integer $R(1 \le R \le 100)$, where $R$ is the number of rows in the grid.The third line of input will be an integer $C(1 \le C \le 100)$, where $C$ is the number of columns in the grid. The remaining input will provide the letters in the grid. It will consist of $R$ lines, where each line contains $C$ uppercase letters separated by single spaces. ## Output The following table shows how the available 15 marks are distributed: | Marks | Word Placement | | :----------: | :---------- | | $2$ | On one horizontal line segment | | $2$ | On one horizontal or vertical line segment | | $2$ | On one horizontal, vertical, or diagonal line segment | | $9$ | On one line segment or two perpendicular line segments | The output will consist of a single non-negative integer $H$, representing the number of times the word is hidden in the grid. [samples] ## Note **本题采用捆绑测试**。 - Subtask $1$（$2$ points）：隐藏字符串一定在一条水平线段上。 - Subtask $2$（$2$ points）：隐藏字符串一定在一个水平或垂直线段上。 - Subtask $3$（$2$ points）：隐藏字符串一定在一个水平、垂直或对角线线段上。 - Subtask $4$（$9$ points）：隐藏字符串一定在一个线段或两个互相垂直的线段上。样例 $1$ 图解： ![](https://cdn.luogu.com.cn/upload/image_hosting/wqo2un8k.png) 样例 $2$ 图解： ![](https://cdn.luogu.com.cn/upload/image_hosting/v082p2qr.png)

Samples

Input #1

MENU
5
7
F T R U B L K
P M N A X C U
A E R C N E O
M N E U A R M
M U N E M N S

Output #1

Input #2

NATURE
6
9
N A T S F E G Q N
S A I B M R H F A
C F T J C U C L T
K B H U P T A N U
D P R R R J D I R
I E E K M E G B E

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CCC 2023 J5] CCC Word Hunt",
    "description": {
      "content": "In the CCC Word Hunt, words are hidden in a grid of letters. The letters of a hidden word always appear in order on horizontal, vertical, or diagonal line segments in one of two ways.One way is for th",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9303"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In the CCC Word Hunt, words are hidden in a grid of letters. The letters of a hidden word always appear in order on horizontal, vertical, or diagonal line segments in one of two ways.One way is for th...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments