首页 > 试题广场 >

字符迷阵

[编程题]字符迷阵
  • 热度指数：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
算法知识视频讲解
添加回答
Python
ElonB头像 ElonB 
""""
固定方向的深度搜索
"""
import sys


def dfs(maze, x, y, word, t):
    if not word:
        return True
    move = [[1, 0], [0, 1], [1, 1]]
    x, y = x + move[t][0], y + move[t][1]
    if x < len(maze) and y < len(maze[0]):
        if maze[x][y] == word[0]:
            return dfs(maze, x, y, word[1:], t)
        else:
            return False
    return False


if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    T = int(input().strip())
    for _ in range(T):
        n, m = list(map(int, input().strip().split()))
        maze = []
        for _ in range(n):
            maze.append(input().strip())
        word = input().strip()
        ans = 0
        for i in range(n):
            for j in range(m):
                if maze[i][j] == word[0]:
                    for t in range(3):
                        if dfs(maze, i, j, word[1:], t):
                            ans += 1
        print(ans)

发表于 2019-07-13 10:40:23 回复(0)
keashem头像 keashem

深搜dfs，不同于一般回溯能走四个方向，这里只能走固定方向，认识到这一点就是常规dfs操作即可，AC代码如下

import java.util.Scanner;
import static java.lang.System.in;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        int n = Integer.parseInt(sc.nextLine());
        while (n-- > 0) {
            count = 0;
            String[] str = sc.nextLine().split(" ");
            int row = Integer.parseInt(str[0]), col = Integer.parseInt(str[1]);
            char[][] data = new char[row][col];
            for (int i = 0; i < row; i++) {
                data[i] = sc.nextLine().toCharArray();
            }
            char[] word = sc.nextLine().toCharArray();
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    for (int k = 0; k <= 2; k++) {
                        dfs(data,word,i,j,0,k);
                    }
                }
            }
            System.out.println(count);
        }
    }

    public static int count = 0;

    public static void dfs(char[][] data, char[] word, int row, int col, int wordPos, int dir) {
        if (wordPos == word.length) {
            count++;
            return;
        }
        if (row == data.length || col == data[0].length) {
            return;
        }
        if (data[row][col] != word[wordPos]) {
            return;
        }
        if (dir == 0) { //向右
            dfs(data, word, row, col + 1, wordPos + 1, dir);
        } else if (dir == 1) { //向下
            dfs(data, word, row + 1, col, wordPos + 1, dir);
        } else if (dir == 2) { //向右下
            dfs(data, word, row + 1, col + 1, wordPos + 1, dir);
        }
    }
}
发表于 2019-08-07 15:56:13 回复(0)
J.Fan头像 J.Fan 
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int T, n, m;
    cin >> T;
    int tmp;
    vector<int> vCount;
    for (int i = 0; i < T; i++)
    {
        cin >> n >> m;
        vector<string> v(n);
        for (int j = 0; j < n; j++)
        {
            cin >> v[j];
        }
        string s;
        cin >> s;
        int len = s.size();
        int ind, row, col;
        int count = 0;
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < m; k++)
            {
                row = j; col = k; ind = 0;
                while (row < n && ind < len && v[row][col] == s[ind])
                {
                    ind++;
                    row++;
                }

                if (ind == len)
                {
                    count++;
                }
                row = j; col = k; ind = 0;
                while (col < m && ind < len && v[row][col] == s[ind])
                {
                    ind++;
                    col++;
                }
                if (ind == len)
                {
                    count++;
                }
                row = j; col = k; ind = 0;
                while (row < n && col < m && ind < len && v[row][col] == s[ind])
                {
                    ind++;
                    row++;
                    col++;
                }
                if (ind == len)
                {
                    count++;
                }
            }
        }
        vCount.push_back(count);
    }
    for (int i = 0; i < T; i++)
    {
        cout << vCount[i] << endl;
    }
    return 0;
}

发表于 2018-08-07 12:34:29 回复(0)
Tsuku_Yomi_头像 Tsuku_Yomi_
对内存命中友好的状态机代码 
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>

char marx[110][110];
char str[10];
bool hax[100][100][10][3];
int t;
int h,w;
using namespace std;

int main(){
    scanf("%d",&t);
    while(t--){
        memset(hax,0,sizeof(hax));
        scanf("%d%d",&h,&w);
        for(int i=1;i<=h;++i){
            scanf("%s",(marx[i]+1));
        }
        long long ans=0;
        scanf("%s",str);
        int len=strlen(str);
        for(int i=1;i<=h;++i){
            for(int r=1;r<=w;++r){
                char tmp=marx[i][r];
                if(tmp==str[0]) hax[i][r][0][0]=hax[i][r][0][1]=hax[i][r][0][2]=true;
                for(int p=1;p<len;++p){
                    if(tmp==str[p]){
                        if(hax[i-1][r][p-1][0]) hax[i][r][p][0]=true;
                        if(hax[i][r-1][p-1][1]) hax[i][r][p][1]=true;
                        if(hax[i-1][r-1][p-1][2]) hax[i][r][p][2]=true;
                    }
                }
                for(int face=0;face<3;++face){
                    if(hax[i][r][len-1][face])ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
}

发表于 2022-02-17 23:59:00 回复(0)
Java
pein531头像 pein531
遍历字符矩阵，匹配到开头字符就从当前位置分别进行往右、往下和往右下的深搜 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            String[] params = br.readLine().split(" ");
            int n = Integer.parseInt(params[0]);
            int m = Integer.parseInt(params[1]);
            char[][] matrix = new char[n][];
            for(int i = 0; i < n; i++){
                matrix[i] = br.readLine().toCharArray();
            }
            char[] target = br.readLine().toCharArray();
            int total = 0;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(matrix[i][j] == target[0]){
                        total += dfs(matrix, i, j, target, 0, "right") + dfs(matrix, i, j, target, 0, "down") + dfs(matrix, i, j, target, 0, "rd");
                    }
                }
            }
            System.out.println(total);
        }
    }
    
    private static int dfs(char[][] matrix, int i, int j, char[] target, int depth, String direction) {
        if(depth == target.length){
            return 1;     // 形成一条有效路径
        }
        if(i >= matrix.length || j >= matrix[0].length || target[depth] != matrix[i][j]){
            return 0;
        }
        // 三个方向有一个能凑出目标词就行
        if("right".equals(direction)){
            return dfs(matrix, i, j + 1, target, depth + 1, direction);
        }else if("down".equals(direction)){
            return dfs(matrix, i + 1, j, target, depth + 1, direction);
        }else{
            return dfs(matrix, i + 1, j + 1, target, depth + 1, direction);
        }
    }
}

发表于 2022-01-08 10:26:19 回复(0)
Python
maoxiaomao头像 maoxiaomao
注意：只能固定一个方向走。。。。。。。
直接定义三个走方向的函数，然后判断走的距离。 
def right(i,j):                          #固定往右走
    num=0
    while i>=0 and i<=row-1 and j>=0 and j<=col-1 and  num<=LW-1 and  word[num]==mat[i][j]:
        num+=1
        j+=1 
    if num==LW:return True  
    return False   
def down(i,j):                           #固定往下走
    num=0
    while i>=0 and i<=row-1 and j>=0 and j<=col-1 and  num<=LW-1 and  word[num]==mat[i][j]:
        num+=1
        i+=1  
    if num==LW:return True  
    return False   
def rdown(i,j):                         #固定往右下走
    num=0
    while i>=0 and i<=row-1 and j>=0 and j<=col-1 and  num<=LW-1 and  word[num]==mat[i][j]:
        num+=1
        j+=1
        i+=1  
    if num==LW:return True  
    return False   

    
T=int(input())          #T组测试用例
for t in range(T): 
    row,col=map(int,input().strip().split())   #row,col记录行数和列数
    mat=[]
    for r in range(row):
        tmp=input().strip() 
        mat.append(tmp) 
    word=input().strip()                       #word存储需要寻找的单词
    if row<=1 and col<=1:                      #特例输入 
        print(0)
        continue
    ans,LW=0,len(word) 
    for i in range(row):
        for j in range(col):
            if mat[i][j]==word[0]:
                if right(i, j):ans+=1 
                if down(i, j):ans+=1
                if rdown(i, j):ans+=1
    print(ans)


编辑于 2021-08-20 11:13:42 回复(0)
C
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
// 这代码至少有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)
小小呆萌坤头像 小小呆萌坤 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

//总结目前牛客问题 第一,没有循环输入问题, 第二 有循环输入问题, 第三 输入有多余空格问题 ,第四 中间插入多余空行问题 ....
namespace Test0001
{
    public struct Vector2
    {
        public int x;
        public int y;
        public Vector2(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }

    class Program
    {
        public static List<Vector2> dir = new List<Vector2>() { new Vector2(0, 0) }; //创建方向
        public static int n, m, count = 0;
        public static void Main(string[] args)
        {
            //string line;
            //while (!string.IsNullOrEmpty(line = Console.ReadLine())) Func(line);
            Func(Console.ReadLine());
        }
        public static void Func(string line)
        {
            int k = int.Parse(line);
            InitDir();//方向向量初始化
            for (int p = 0; p < k; p++)
            {
                var s1 = Console.ReadLine().Trim().Split(' ').Select(x=>int.Parse(x)).ToArray();
                m = s1[0]; 
                n = s1[1];
                
                //初始化地图
                char[,] map = new char[n, m];
                for (int j = 0; j < m; j++)
                {
                    var s2 = Console.ReadLine().Trim().ToArray();
                    for (int i = 0; i < n; i++)
                    {
                        map[i, j] = s2[i];
                    }
                }
              
                string word = Console.ReadLine().Trim();
                int sum = 0;//单词总个数
                //遍历地图
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < m; j++)
                    {
                        count = 0;
                        if (map[i,j] == word[0])//找到起点
                        {
                            FindWord(i, j, 0, 0, word, map);//从起点开始朝8个方向遍历
                            sum += count;//一个起点可能有多个单词
                        }
                    }
                }
                Console.WriteLine(sum);
            }
        }

        static void FindWord(int x, int y, int r, int index, string word,char[,] map)
        {
            if (!IsXRange(x) || !IsYRange(y) || index >= word.Length) return;
            
            if (r == 0) //向所有方向开始遍历
            {
                for (int i = 1; i <dir.Count ; i++)//向8个方向开始遍历
                {
                    FindWord(x + dir[i].x, y + dir[i].y, i, index + 1, word, map);
                }
            }
            else //固定方向
            {
                if(word[index] == map[x, y])
                {
                    if (index == word.Length - 1) //说明单词正确
                    {
                        count++;
                        return;
                    }
                    FindWord(x + dir[r].x, y + dir[r].y, r, index + 1, word, map);
                }
            }
        }
       
        /// <summary>
        /// 初始化方向
        /// </summary>
        public static void InitDir()
        {
            //方向{0,0},{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}
            //     所有   右    左     下    上    右下  右上   左下    左上
           
            //8方向
            /* for (int i = -1; i <= 1; i++)
             {
                 for (int j = -1; j <= 1; j++)
                 {
                     if (i == 0 && j == 0) continue;
                     dir.Add(new Vector2(i, j));
                 }
             }*/
           
            //选取右方、下方、或右下45度方向作为单词的延伸方向；
            dir.Add(new Vector2(1, 0)); //右
            dir.Add(new Vector2(0, 1)); //下
            dir.Add(new Vector2(1, 1)); //右下
        }

        /// <summary>
        /// X边界
        /// </summary>
        /// <param name="val"></param>
        /// <returns></returns>
        public static bool IsXRange(int val)
        {
            return val >= 0 && val < n;
        }
     
        /// <summary>
        /// Y边界
        /// </summary>
        /// <param name="val"></param>
        /// <returns></returns>
        public static bool IsYRange(int val)
        {
            return val >= 0 && val < m;
        }

    }
}
创建生成地图,之后以目标单词开头第一个字母为起点,遍历地图找到所有起点,分别向题目要求方向遍历即可,这题我这样写可以做到向任意方向遍历,而且修改起来也比较方便,直接修改方向数组即可
方向用数组存放(我这里用List集合) 
//方向{0,0},{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}
//     所有   右    左     下    上    右下  右上   左下    左上
(创建的矩阵不同方向可能不同)
r就是方向 当r=0的时候他会朝所有方向开始遍历,并且将r变为该方向,在之后的递归中由于r!=0所以就形成了朝一个方向遍历
编辑于 2019-12-11 09:34:18 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int n,m;
char G[101][101];

int F(int x, int y, string s){
    int i, cnt=0, l=s.length();
    for(i=1;i<l && y+i<m;i++)
        if(G[x][y+i]!=s[i])
            break;
    cnt += (i==l);
    for(i=1;i<l && x+i<n;i++)
        if(G[x+i][y]!=s[i])
            break;
    cnt += (i==l);
    for(i=1;i<l && x+i<n && y+i<m;i++)
        if(G[x+i][y+i]!=s[i])
            break;
    cnt += (i==l);
    return cnt;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>G[i][j];
        string s;
        cin>>s;
        int l=s.length(), cnt=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(G[i][j]==s[0])
                    cnt += F(i,j,s);
        cout<<cnt<<endl;
    }
    return 0;
}

发表于 2019-12-01 19:30:12 回复(0)
C/C++
Andrew_Y头像 Andrew_Y 
暴力求解，貌似没有太好的办法
#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main()
{
    int T;
    cin>>T;
    for(int i=0;i<T;i++)
    {
        int m,n;
        cin>>m>>n;
        vector<string> a;
        string input;
        string word;
        int num=0;
        for(int j=0;j<m;j++)
        {
            cin>>input;
            a.push_back(input);
        }
        cin>>word;
        int len=word.size();
        for(int r=0;r<m;r++)
        {
            for(int c=0;c<n;c++)
            {
                string tmp;
                int r_cur=r;
                int c_cur=c;
                //向下
                while((r_cur<r+len)&&(r+len<=m))
                {
                    tmp+=a[r_cur][c];
                    r_cur++;
                }
                if(tmp==word)
                    num++;
                //复位
                tmp.clear();
                r_cur=r;
                c_cur=c;
                //向右
                while((c_cur<c+len)&&(c+len<=n))
                {
                    tmp+=a[r][c_cur];
                    c_cur++;
                }
                if(tmp==word)
                    num++;
                //复位
                tmp.clear();
                r_cur=r;
                c_cur=c;
                //右下
                while((c_cur<c+len)&&(r_cur<r+len)&&(r+len<=m)&&(c+len<=n))
                {
                    tmp+=a[r_cur][c_cur];
                    r_cur++;
                    c_cur++;
                }
                if(tmp==word)
                    num++;
            }
        }
        cout<<num<<endl;
    }
}

发表于 2019-10-16 21:43:52 回复(0)
C/C++
SuperAidenGreen头像 SuperAidenGreen
如果双重循环还是不能解决问题，那就再循环一次  ——鲁迅 
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main() {
	int eNum = 0;
	scanf("%d", &eNum);
	while (eNum != 0) {
		eNum--;
		int w, h = 0;
		scanf("%d %d\n", &h, &w);
		vector<string> matrix;
		for (int i = 0; i < h; i++) {
			string temp;
			getline(cin, temp);
			matrix.push_back(temp);
		}
		string tag;
		getline(cin, tag);
		int count = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				for (int k = 0; k <= tag.size() && j + k < w; k++) {
					if (matrix[i][j+k] != tag[k])
						break;
					if (k + 1 == tag.size())
						count++;
				}
				for (int k = 0; k <= tag.size() && i + k < h; k++) {
					if (matrix[i+k][j] != tag[k])
						break;
					if (k + 1 == tag.size())
						count++;
				}
				for (int k = 0; k <= tag.size() && i + k < h && j + k < w; k++) {
					if (matrix[i + k][j + k] != tag[k])
						break;
					if (k + 1 == tag.size())
						count++;
				}

			}
		}
		cout << count << endl;
	}
}


编辑于 2019-09-26 21:15:26 回复(0)
皮蛋秀柚秋头像 皮蛋秀柚秋 
#include<bits/stdc++.h>
using namespace std;
#define N 100
int main()
{
    int n;
    int a,b;
    int k,x,y;
     // 遍历一个二维数组 往三个方向搜一遍即可  代码有点粗糙。。
    char matrix[N][N];
    string s;
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        for(int i=0;i<a;i++)
            for(int j=0;j<b;j++)
                cin>>matrix[i][j];
        cin>>s;
        int len = s.size();
        int cnt = 0;
        for(int i=0;i<a;i++)
            for(int j=0;j<b;j++)
            {
                if(s[0]==matrix[i][j])
                {
                    // 右
                    k = 0,x = i,y = j;
                    while(k<len&&y<b)
                    {
                        if(matrix[x][y]==s[k])
                        {
                            y++;
                            k++;
                        }
                           
                        else break;
                            
                    }
                    if(k==len) cnt++;
                     // 下
                     k = 0,x = i,y = j;
                     while(k<len&&x<a)
                    {
                        if(matrix[x][y]==s[k])
                        {
                            x++;
                            k++;
                        }
                           
                        else break;
                            
                    }
                    if(k==len) cnt++;
                    //右下
                     k = 0,x = i,y = j;
                     while(k<len&&x<a&&y<b)
                    {
                        if(matrix[x][y]==s[k])
                        {
                            x++;
                            y++;
                            k++;
                        }
                           
                        else break;
                            
                    }
                    if(k==len) cnt++;
                    
                    
                }
            }
        cout<<cnt<<endl;
        
        
    }
    return 0;
}

发表于 2019-08-07 20:21:41 回复(0)
紫气头像 紫气 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int group_len = sc.nextInt();
        char[][][] groups = new char[group_len][][];
        String[] key_world = new String[group_len];
        for (int i = 0; i < group_len; i++) {
            int row_len = sc.nextInt();
            int col_len = sc.nextInt();
            groups[i] = new char[row_len][col_len];
            for (int j = 0; j < row_len; j++) {
                String line = sc.next();
                for (int col = 0; col < col_len; col++) {
                    groups[i][j][col] = line.charAt(col);
                }
            }
            key_world[i] = sc.next();
        }
        sc.close();
        for(int i = 0; i < group_len; i++){
            char[][] group = groups[i];
            int result = 0;
            String key = key_world[i];
            for(int row = 0; row < group.length; row++){
                char[] cols = group[row];
                for(int col = 0; col < cols.length; col++){
                    if(cols[col] == key.charAt(0)){
                        if(col <= cols.length - key.length()){
                            StringBuilder sb = new StringBuilder();
                            for(int s_index = 0; s_index < key.length(); s_index++){
                                sb.append(group[row][col + s_index]);
                            }
                            if(sb.toString().equals(key)) result++;
                        }
 
                        if(row <= group.length - key.length()){
                            StringBuilder sb = new StringBuilder();
                            for(int s_index = 0; s_index < key.length(); s_index++){
                                sb.append(group[row + s_index][col]);
                            }
                            if(sb.toString().equals(key)) result++;
                        }
 
                        if(row <= group.length - key.length() && col <= cols.length - key.length()){
                            StringBuilder sb = new StringBuilder();
                            for(int s_index = 0; s_index < key.length(); s_index++){
                                sb.append(group[row + s_index][col + s_index]);
                            }
                            if(sb.toString().equals(key)) result++;
                        }
 
                    }
                }
            }
            System.out.println(result);
        }
 
 
 
 
    }
}

发表于 2019-07-10 12:00:45 回复(0)
Mono_Chrome头像 Mono_Chrome 
import java.util.Scanner;

public class Main {

    public static int process(char[][] ch, String word, int i, int j, int len, int type) {
        if (len == word.length()) {
            return 1;
        }
        if (i < 0 || i >= ch.length || j < 0 || j >= ch[0].length || ch[i][j] != word.charAt(len)) {
            return 0;
        }

        int length = 0;
        if (ch[i][j] == word.charAt(len)) {
            switch (type) {
                case 0:
                    length += process(ch, word, i + 1, j, len + 1, 0);
                    break;
                case 1:
                    length += process(ch, word, i, j + 1, len + 1, 1);
                    break;
                case 2:
                    length += process(ch, word, i + 1, j + 1, len + 1, 2);
                    break;
            }
        }
        return length;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            char[][] ch = new char[m][n];
            for (int i = 0; i < m; i++) {
                ch[i] = sc.next().toCharArray();
            }
            String word = sc.next();
            int sum = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sum += process(ch, word, i, j, 0, 0) +
                            process(ch, word, i, j, 0, 1) +
                            process(ch, word, i, j, 0, 2);
                }
            }
            System.out.println(sum);
        }
    }
}
发表于 2019-07-06 20:00:10 回复(0)
ABCNB头像 ABCNB
# 给出python代码，以供参考
# 思路为，首先找到单词的第一个字符
# 然后分别找三个方向 按照单词长度 取出三个方向的字符进行比较 相同则加一
# 要先设置边界条件：即当三个方向还有单词长度的空位
t=int(input())
foriinrange(t):
    mat=[]
    count=0
    m,n=map(int,input().split(' '))
    foriinrange(m):
        mat.append(input())
    key=input()
 
    foriinrange(m):
        forjinrange(n):
            ifmat[i][j]==key[0]:
                ifn-j>=len(key):
                    s1=''
                    forkinrange(len(key)):
                        s1+=mat[i][j+k]
                    ifs1==key:
                        count+=1
                ifm-i>=len(key):
                    s2=''
                    forlinrange(len(key)):
                        s2+=mat[i+l][j]
                    ifs2==key:
                        count+=1
                ifn-j>=len(key)andm-i>=len(key):
                    s3=''
                    forpinrange(len(key)):
                        s3+=mat[i+p][j+p]
                    ifs3==key:
                        count+=1
    print(count)
发表于 2018-11-07 17:41:17 回复(0)
宇宙第二菜鸡头像 宇宙第二菜鸡 
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int q = 0; q < n; q++){
        int width, height;
        cin >> width >> height;
        vector<string> maze(width);
        for (int i = 0; i < width; i++){
            string tmp;
            cin >> tmp;
            maze[i] = tmp;
        }
        string key;
        cin >> key;

        int count = 0;
        for (int i = 0; i < width; i++){
            for (int j = 0; j < height; j++){
                if (maze[i][j] == key[0]){
                    for (int m = 1; m < key.size(); m++){
                        if (j + m >= height)break;
                        if (maze[i][j + m] != key[m])break;
                        if (m == key.size() - 1)count++;
                    }
                    for (int m = 1; m < key.size(); m++){
                        if (i + m >= width)break;
                        if (maze[i + m][j] != key[m])break;
                        if (m == key.size() - 1)count++;
                    }
                    for (int m = 1; m < key.size(); m++){
                        if (i + m >= width || j + m >= height)break;
                        if (maze[i + m][j + m] != key[m])break;
                        if (m == key.size() - 1)count++;
                    }
                }
            }
        }

        cout << count << endl;
    }

    return 0;
}

发表于 2018-08-03 23:20:16 回复(1)
lentolove头像 lentolove 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    /**
     * 本来以为是一个标准的回溯题，遍历，一顿操作之后测试第三个测试用例输出 47
     * 题目不同于图的遍历里的任意方向的搜索，而是每次按照一个固定方向的深度搜索。
     * 每次第一个字符串匹配后沿着三个方向搜索一下就行了。
     */
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(bf.readLine());
        for (int i = 0; i < t; i++) {
            String[] line1 = bf.readLine().split(" ");
            int m = Integer.parseInt(line1[0]);//行数
            int n = Integer.parseInt(line1[1]);//列数
            char[][] matrix = new char[m][n];
            for (int j = 0; j < m; j++) {
                matrix[j] = bf.readLine().toCharArray();
            }
            String target = bf.readLine();//匹配的字符
            int count = 0;
            for (int j = 0; j < m; j++) {//行
                for (int k = 0; k < n; k++) {//列
                    //注意这个题不同于普通的回溯搜索题，这个是固定的方向
                    if (matrix[j][k] == target.charAt(0)) {
                        //方向一:向右方向
                        for (int p = 1; p < target.length(); p++) {
                            if (p + k >= n) break;
                            if (matrix[j][p + k] != target.charAt(p)) break;
                            if (p == target.length() - 1) count++;
                        }
                        //方向二:向下方向
                        for (int p = 1; p < target.length(); p++) {
                            if (p + j >= m) break;
                            if (matrix[p + j][k] != target.charAt(p)) break;
                            if (p == target.length() - 1) count++;
                        }

                        //方向三：右下方向
                        for (int p = 1; p < target.length(); p++) {
                            if (p + j >= m || p + k >= n) break;
                            if (matrix[j + p][k + p] != target.charAt(p)) break;
                            if (p == target.length() - 1) count++;
                        }
                    }
                }
            }
            System.out.println(count);
        }
    }

    //不能用这个
    private static int wordCount(char[][] matrix, int m, int n, int i, int j, String target, int len, int count) {
        if (i >= m || j >= n || matrix[i][j] != target.charAt(len)) return 0;
        if (len == target.length() - 1) {
            return 1;
        }
        return wordCount(matrix, m, n, i, j + 1, target, len + 1, count) +
                wordCount(matrix, m, n, i + 1, j, target, len + 1, count)
                + wordCount(matrix, m, n, i + 1, j + 1, target, len + 1, count);
    }
}
发表于 2019-08-06 16:18:18 回复(1)
Ⅲ_Dc头像 Ⅲ_Dc 
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

class solution
{
    public:
    int count;
    vector<vector<char> > ss;
    string str;
    public:
    void deal(int i,int j,int now,int type)
    {
    if(i<=ss.size()-1&&j<=ss[i].size()-1)
    {
        if(ss[i][j]==str[now])
        {
            if(now==str.size()-1) count++;
            
            switch(type)
            {
                case 1:deal(i+1,j+1,now+1,1);break;
                case 2:deal(i,j+1,now+1,2);break;
                case 3:deal(i+1,j,now+1,3);break;
                default:break;
            }
        }
    }

    }
};

int main(void)
{
    int len,wid,num;
    cin>>num;
    solution s;
    string str_;
    while(num--)
    {
        
        cin>>len>>wid;
        vector<vector<char> > table(len,vector<char>(wid,0));
        for(int i=0;i<=len-1;i++)
        {
            for(int j=0;j<=wid-1;j++)
            {
                cin>>table[i][j];
                //cout<<table[i][j];
            }
           //cout<<endl;
        }
         //cout<<"................"<<endl;
        
        cin>>str_;
        //cout<<"str:"<<str_<<endl;
        
         //cout<<"................"<<endl;
        
        s.str = str_;
        s.count = 0;
        s.ss = table;
        
    for(int i=0;i<=len-1;i++)
      for(int j=0;j<=wid-1;j++)
          {
            s.deal(i, j, 0,1);
            s.deal(i, j, 0,2);
            s.deal(i, j, 0,3);
          }
        
       cout<<s.count<<endl;
        
        
    }
    
    return 0;
}

发表于 2022-02-27 23:11:52 回复(0)
C/C++
kpl第一韩信头像 kpl第一韩信
#include <iostream>
#include <string>
using namespace std;

int main()
{
    int t,m,n;
    char x;
    string s;
    cin>>t;
    while(t--){
        int count =0;
        cin>>m>>n;
        char a[m][n];
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                cin>>x;
                a[i][j]=x;
            }
        cin>>s;
        int length=s.length();

        for(int i=0;i<=m-length;i++)
        for(int j=0;j<=n-length;j++){
            string s1;
            string s2;
            string s3;
            for(int k=0;k<length;k++){
                s1.append(1,a[i][j+k]);
                s2.append(1,a[i+k][j]);
                s3.append(1,a[i+k][j+k]);
                if(s.compare(s1)==0)
                    count++;
                if(s.compare(s2)==0)
                    count++;
                if(s.compare(s3)==0)
                    count++;
            }
        }
        for(int i=m-length+1;i<m;i++)
        for(int j=0;j<=n-length;j++){
            string s4;
            for(int k=0;k<length;k++){
                s4.append(1,a[i][j+k]);
                if(s.compare(s4)==0)
                    count++;
            }
        }
        for(int i=0;i<=m-length;i++)
        for(int j=n-length+1;j<n;j++){
            string s5;
            for(int k=0;k<length;k++){
                s5.append(1,a[i+k][j]);
                if(s.compare(s5)==0)
                    count++;
            }
        }
        cout<<count<<endl;
    }
}
发表于 2021-04-07 11:15:58 回复(0)
lpossible头像 lpossible 
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int m, n;
        cin >> m >> n;
        vector<string> v(m);
        for (int i = 0; i < m; i++)
        {
            cin >> v[i];
        }
        string s;
        cin >> s;
        int count = 0;
        int len = s.length();
        char c = s[0];
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (v[i][j] == c)
                {
                    //向右
                    int index1 = j + len - 1;
                    //向下
                    int index2 = i + len - 1;
                    if (index1 < n)
                    {
                        string temp = v[i].substr(j, len);
                        if (temp == s) count++;
                    }
                    if (index2 < m)
                    {
                        string temp;
                        for (int k = i; k <= index2; k++)
                        {
                            temp.push_back(v[k][j]);
                        }
                        if (temp == s) count++;
                    }
                    if (index1 < n && index2 < m)
                    {
                        string temp;
                        int p = i, q = j;
                        while (p<=index2&&q<=index1)
                        {
                            temp.push_back(v[p][q]);
                            p++;
                            q++;
                        }
                        if (temp == s) count++;
                    }
                }
            }
        }
        cout << count << endl;
    }
}
发表于 2021-03-22 21:51:31 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

字符迷阵

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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