字符迷阵

[编程题]字符迷阵

热度指数：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

算法知识视频讲解

Java

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)

Java

4CTOR

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();
        for(int i = 0; i < total; i++){

            int row = scanner.nextInt();
            int col = scanner.nextInt();
            char[][] matirx = new char[row][col];

            //存入矩阵
            for(int j = 0; j < row; j++){
                matirx[j] = scanner.next().toCharArray();
            }
            char[] word = scanner.next().toCharArray();

            System.out.println(heng(matirx, word, row, col)+xie(matirx, word, row, col)+shu(matirx, word, row, col));

        }
    }

    public static int heng(char[][] matirx, char[] word, int row, int col){
        int sum = 0;
        for(int i = 0; i < row; i++){
            for(int j = 0; j <= col - word.length; j++){
                if(matirx[i][j] == word[0]){
                    int k = 1;
                    for(k = 1; k < word.length-1; k++){
                        if(matirx[i][j + k] != word[k]){
                            break;
                        }
                    }
                    if(k == word.length - 1&&matirx[i][j + k] == word[k]){
                        sum++;
                    }
                }
            }
        }
        return sum;
    }

    public static int shu(char[][] matirx, char[] word, int row, int col){
        int sum = 0;
        for(int i = 0; i < col; i++){
            for(int j = 0; j <= row - word.length; j++){
                if(matirx[j][i] == word[0]){
                    int k = 1;
                    for(k = 1; k < word.length-1; k++){
                        if(matirx[j+k][i] != word[k]){
                            break;
                        }
                    }
                    if(k == word.length - 1&&matirx[j+k][i] == word[k]){
                        sum++;
                    }
                }
            }
        }
        return sum;
    }

    public static int xie(char[][] matirx, char[] word, int row, int col){
        int sum = 0;
        for(int i = 0; i<=row-word.length; i++){
            for(int j = 0; j <= col - word.length; j++){
                if(matirx[i][j] == word[0]){
                    int k = 1;
                    for(k = 1; k < word.length-1; k++){
                        if(matirx[i+k][j+k] != word[k]){
                            break;
                        }
                    }
                    if(k == word.length - 1&&matirx[i+k][j+k] == word[k]){
                        sum++;
                    }
                }
            }
        }
        return sum;
    }

}

编辑于 2020-08-11 14:44:03 回复(0)

Java

叮咚片

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {

   public static void main(String[] args) {

       Scanner sc = new Scanner(System.in);
       int T = sc.nextInt();
       int i, j, h, l, k;
       String word;
       int count=0;

       while (T > 0) {
           h = sc.nextInt();
           l = sc.nextInt();

           char[][] carr = new char[h][l];
           String str;
           sc.nextLine();
           for (i = 0; i < h; i++) {

               str = sc.nextLine();
               carr[i] = str.toCharArray();

           //   System.out.println(Arrays.toString(carr[i]));

           }

           word = sc.nextLine();
           //System.out.println(word + "   " + word.length());
           int th, tl, p = 0;

           for (i = 0; i < h; i++) {
               for (j = 0; j < l; j++) {

                   if (carr[i][j] == word.charAt(0)) {

                       // 向右寻找，
                       th = i;
                       tl = j;
                       while (p < word.length() && tl + p < l && carr[th][tl + p] == word.charAt(p)) {

                           p++;

                       }
                       if (p == word.length()) {

                       //   System.out.println("to the left h= " + i + " l= " + j);
                           count++;
                       }

                       p = 0;

                   }

                   if (carr[i][j] == word.charAt(0)) {

                       // DOWN
                       th = i;
                       tl = j;
                       while (p < word.length() && th + p < h && carr[th + p][tl] == word.charAt(p)) {

                           p++;

                       }
                       if (p == word.length()) {

                       //   System.out.println("to the down h= " + i + " l= " + j);
                           count++;
                       }

                       p = 0;
                   }

                   if (carr[i][j] == word.charAt(0)) {

                       // DOWN and left
                       th = i;
                       tl = j;
                       while (p < word.length() && th + p < h && tl + p < l
                               && carr[th + p][tl + p] == word.charAt(p)) {

                           p++;

                       }
                       if (p == word.length()) {

                       //   System.out.println("to the down and left h= " + i + " l= " + j);
                           count++;
                       }

                       p = 0;
                   }

               }

           }
           System.out.println(count);
           count=0;
            T--;
       }

   }
}

发表于 2020-06-02 16:02:52 回复(0)