首页 > 试题广场 >

字符迷阵

[编程题]字符迷阵
  • 热度指数：7144 时间限制：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
算法知识视频讲解
开通博客
头像 白伟仝
发表于 2020-05-09 12:50:37
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int T = sc.nex 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Ⅲ_Dc
发表于 2022-03-07 14:20:10
// #include <iostream> #include <vector> #include <string> #include <map> using namespace std; class solution { public: 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客题解官
发表于 2020-06-05 16:12:45
题解 题目难度：简单 知识点：DFS、字符串、 方法（一）： 第一步：获取单词的首字符第二步：在字符迷阵中找到该字符第三步：字符迷阵中从该字符开始，从水平、垂直、右下角方向与单词字符逐一比较【注1】：在逐一比较时要考虑字符迷阵的边界，即m、n，访问字符迷阵时数组越界问题。【注2】：当我们在考虑三个方 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 模拟 字符串 网易互娱 2018 2019 游戏研发工程师 查找 Java工程师
上传者：牛客299770号
难度：
66条回答 8524浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号