字符迷阵

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)

k = int(input())
for _ in range(k):
    m,n= map(int,input().split())
    parten = []
    for i in range(m):
        tmp = []
        ss = input()
        for j in range(n):
            tmp.append(ss[j])
        parten.append(tmp)
    word = input()       
    def dfs(parten,word,i,j,c,dx,dy):
        if not word:
            c+=1                    
            return c
        if i<0 or i>=len(parten) or j<0 or j>=len(parten[0]) :
            return c
        if parten[i][j]==word[0]:
            c = dfs(parten,word[1:],i+dx,j+dy,c,dx,dy)
        return c

    dx,dy,ans = [0,1,1],[1,0,1],0
    for i in range(m):
        for j in range(n):
            for t in range(3):
                num = dfs(parten,word,i,j,0,dx[t],dy[t])
                ans += num
    print(ans)

# 暴力破解法   
#  注意：1.当剩余行列不足要查找单词长度时，对应的下方和右下方一定不存在要查找的单词
#       2.注意一行中可能会多次出现要查找单词的首字母
t = int(input()) # 测试数据组数
for _ in range(t):
    m,n = map(int,input().split()) #读取行数和列数
    matrix = [] # 用于存放字符矩阵
    for _ in range(m): #读取字符矩阵
        matrix.append(input())
    word = input() # 读取要查找的单词
    length = len(word) #要查找单词的长度
    res = 0
    for i in range(m): #按列查找
        index = matrix[i].find(word[0]) #查找首字母出现在该行的位置
        while index != -1: #首字母出现在该行,则分别向右、向下以及向右下三个方向进行查找
            if matrix[i].find(word,index,index+length) != -1:  #向右
                res += 1
            if m - i >= length: # 只有当剩余行长度大于等于要查找单词长度时，才有可能在下方存在要查找单词
                j = 1  #向下
                while j < length: 
                    if matrix[i + j][index] != word[j]:
                        j = -1
                        break
                    j += 1
                if j != -1:
                    res += 1
                if n - index >= length:# 只有当剩余行和列长度均大于等于要查找单词长度时，才有可能在右下方存在要查找单词
                    j = 1  #向右下
                    while j < length:
                        if matrix[i + j][index +j] != word[j]:
                            j = -1
                            break
                        j += 1
                    if j != -1:
                        res += 1
            matrix[i] = matrix[i][:index] + 'a' + matrix[i][index + 1:]
            index = matrix[i].find(word[0])
    print(res)