c++ - 给定一个大小为 N*N 的矩阵。我们需要找出特定字符串的位置数

Question

正如问题的标题所示，我们必须找到大小为 N(<=1000) 的字符网格中特定字符串出现的次数。我们只能斜着走。例如

  5               //N
  B X A X X       //grid
  X A X X X       
  X B B X X
  X A X A X
  X X B X X
  ABA           //Finding its occurence in the above grid 

  Answer is 14 

我不知道如何解决这个问题。我见过有人用某种递归来做这件事(他们说这是回溯)。

到目前为止我做了什么

我尝试使用 BFS 解决这个问题，它对小的情况给出了正确的答案，但对大的 N 没有给出任何答案。

我尝试过的 BFS 代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define nline puts("\n")
vector<pair<int,int> >v;
#define e .00000001
string s;
char ch[1000][1000];
int dx[4] = {1, 1, -1, -1};
int dy[4] = { -1, 1, 1, -1 };
char vis[1000][1000];
int n,total=0;
struct data
{
    int x,y;
    void set(int _x,int _y)
    {
        x=_x;
        y=_y;
    }
};

void bfs(data src)
{
    vis[src.x][src.y]=true;
    queue<data>Q;
    Q.push(src);
    int len=1;
    while(not Q.empty())
    {
        data ss=Q.front();
        Q.pop();
        for(int i=0;i<4;i++)
        {
            int xx=dx[i]+ss.x;
            int yy=dy[i]+ss.y;
            if(len<=s.length()-1 and ch[xx][yy]==s[len] and xx>=0 and xx<n and yy>=0 and yy<n and (not vis[xx][yy]))
            {
                vis[xx][yy]=true;
                data tem;
                tem.set(xx,yy);
                Q.push(tem);
                len++;
            }
        }
    }
      if(len==s.length())total++;
}
int main() {
    cin>>n;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    cin>>ch[i][j];
   cin>>s;
   for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
       {
           if(ch[i][j]==s[0])
          {
               data start;
               start.set(i,j);
               bfs(start);
               memset(vis,0,sizeof vis);
          }
       }
    }
      cout<<total<<endl;
      return 0;
}

谁能帮帮我？ :)

Answer 1

递归解决方案，不是您要求的，但我希望它能有所帮助。

我们将使用一个函数来检查矩阵的每个元素出现了多少次。如果 grid[1][1] 匹配字符串的第一个字符，我们需要检查对角线相邻元素是否匹配字符串的第二个字符。我们可以删除字符串的第一个字符，然后使用新字符串简单地对相邻元素调用相同的函数。

(Python 代码，但即使您不了解 Python 也应该是可以理解的)

首先我们创建一个辅助函数来返回有效的对角邻居。

def valid_neighbors(i,j, N):
    # Returns a list of valid diagonal neighbors(Do not exceed matrix borders).
    neighbors = [(i-1, j-1), (i+1, j+1), (i+1, j-1), (i-1, j+1)]
    return [m for m in neighbors if  (0 <= m[0] < N) and (0 <= m[1] < N)]

接下来是检查出现的递归函数(注释解释逻辑)。

def find(matrix, N, i, j, string):
    occurrences = 0
    if string == matrix[i][j]:
        # Found one occurrence, nothing else to do.
        return 1
    if string[0] == matrix[i][j]:
        # First letter of the string match, seek for possible occurrences.
        for new_i, new_j in valid_neighbors(i, j, N):
            # Go over all valid diagonal moves
            if matrix[new_i][new_j] == string[1]:
                # If the char in the new location match the next character of the string,
                # recursively call this function with the new position and the input string
                # minus the first character ("ABCD" -> "BCD").
                occurrences += find(matrix, N, new_i, new_j, string[1:])
    # Finally return the number of occurrences found.
    return occurrences

这适用于矩阵的单个元素，我们需要为每个元素调用该函数并对结果求和。

def wrapper(matrix, string):
    # Call find on every element of the matrix and sum the results.
    occurrences = 0
    N = len(matrix)
    for i in range(N):
        for j in range(N):
            occurrences += find(matrix, N, i, j, string)
    return occurrences

您可以构建一个缓存机制来提高性能。

在输入矩阵上运行代码:

mat = [
       ['B', 'X', 'A', 'X', 'X'],
       ['X', 'A', 'X', 'X', 'X'],
       ['X', 'B', 'B', 'X', 'X'],
       ['X', 'A', 'X', 'A', 'X'],
       ['X', 'X', 'B', 'X', 'X']
       ]
print wrapper(mat, "ABA")
14