字符迷阵

[编程题]字符迷阵

热度指数：7224 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

注意：本题允许使用C/C++/Java/python进行解答，其他编程语言提交均视作无效处理。

字符迷阵是一种经典的智力游戏。玩家需要在给定的矩形的字符迷阵中寻找特定的单词。

在这题的规则中，单词是如下规定的：

1. 在字符迷阵中选取一个字符作为单词的开头；

2. 选取右方、下方、或右下45度方向作为单词的延伸方向；

3. 以开头的字符，以选定的延伸方向，把连续得到的若干字符拼接在一起，则称为一个单词。

以图1为例，如果要在其中寻找单词"WORD"，则绿色框所标示的都是合法的方案，而红色框所标示的都是不合法的方案。

现在的问题是，给出一个字符迷阵，及一个要寻找的单词，问能在字符迷阵中找到多少个该单词的合法方案。注意合法方案是可以重叠的，如图1所示的字符迷阵，其中单词"WORD"的合法方案有4种。

输入描述:

输入的第一行为一个正整数T，表示测试数据组数。 接下来有T组数据。每组数据的第一行包括两个整数m和n，表示字符迷阵的行数和列数。接下来有m行，每一行为一个长度为n的字符串，按顺序表示每一行之中的字符。再接下来还有一行包括一个字符串，表示要寻找的单词。  数据范围： 对于所有数据，都满足1<=T<=9，且输入的所有位于字符迷阵和单词中的字符都为大写字母。要寻找的单词最短为2个字符，最长为9个字符。字符迷阵和行列数，最小为1，最多为99。 对于其中50%的数据文件，字符迷阵的行列数更限制为最多为20。

输出描述:

对于每一组数据，输出一行，包含一个整数，为在给定的字符迷阵中找到给定的单词的合法方案数。

示例1

输入

3
10 10
AAAAAADROW
WORDBBBBBB
OCCCWCCCCC
RFFFFOFFFF
DHHHHHRHHH
ZWZVVVVDID
ZOZVXXDKIR
ZRZVXRXKIO
ZDZVOXXKIW
ZZZWXXXKIK
WORD
3 3
AAA
AAA
AAA
AA
5 8
WORDSWOR
ORDSWORD
RDSWORDS
DSWORDSW
SWORDSWO
SWORD

输出

4
16
5

算法知识视频讲解

勇敢牛牛，不怕困难！

// 这代码至少有10年的功力
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

const int DIRS[][2] = { {1, 0}, {0, 1}, {1, 1} }; // right, down, right-bottom 

const int N = 100;
char matrix[N][N];

// ==================== The Start of Function Declaration ====================
size_t str_len(const char* s) {
  assert(s != NULL);
  if (!*s) return 0;
  const char* p = s;
  while (*++p);
  return p - s;
}

bool inArea(int x, int y, const int m, const int n) {
  return x >= 0 && x < n && y >= 0 && y < m;
}

bool match(int m, int n, int x, int y, int dx, int dy, const char* word, const int len) {
  int p = 0;
  while (inArea(x, y, m, n)
         && p < len && *(*(matrix + y) + x) == *(word + p)) {
    x += dx; y += dy;
    ++p;
  }
  return p == len;
}
// ==================== The End of Function Declaration ====================

int main(const int argc, const char* const argv[]) {
  int t, m, n, x, y;
  fscanf(stdin, "%d", &t);
  while (t--) {
    fscanf(stdin, "%d %d\n", &m, &n);
    for (y = 0; y < m; ++y) {
      for (x = 0; x < n; ++x)
        fscanf(stdin, "%c", *(matrix + y) + x);
      getchar();
    }
    
    char word[10];
    fscanf(stdin, "%s", word);
    
    int i, cnt = 0, len = str_len(word);
    for (y = 0; y < m; ++y)
      for (x = 0; x < n; ++x)
        for (i = 0; i < 3; ++i)
          cnt += match(m, n, x, y, DIRS[i][0], DIRS[i][1], word, len);
    
    fprintf(stdout, "%d\n", cnt);
  }
  
  return 0;
}

发表于 2021-08-11 16:48:13 回复(0)