【python】屈小原求三峡大学面积（CTGU百年校庆）

题目：

"""

题目描述：

屈小原希望你能帮他求出一块地图中学校的面积。地图由nxm个方格组成，每个方格中都有一个小写的英文字母，如果该方格为学校所属，那么该方格必定是一段连续的ctgu的组成部分。从一个特定的字符开始，可以向上、下、左、右四个方向移动到相邻的方格。如果按照这种方式，能够从一个字符按顺序走到另一个字符，形成指定的字符串序列（在这个情况下是“ctgu”），那么这些方格被认为是连续的，即它们是学校的一部分。

输入：

第一行包含两个整数n，m(1

输出：

对于每组测试数据，输出学校所占的方格数目。

样例1：

4 4

cbug

tgtc

gutc

cgtu

样例输出：

7

"""

代码：

"""
思路：深度优先搜索（DFS）
"""
N = 1000  # 设置二维数组的最大维度。预分配空间
# 在绝大多数情况下，上下左右移动的坐标变化确实应该是 (0, 1)、(0, -1)、(1, 0) 和 (-1, 0)。
dx = [0, 0, 1, -1]  # 定义了在x方向上的四个可能的移动（上下左右）
dy = [1, -1, 0, 0]  # 定义了在y方向上的四个可能的移动
ctgu = "ctgu"  # 目标字符串
# 初始化一个二维字符数组s，用于存储输入的字符数据
s = [['' for _ in range(N)] for _ in range(N)]  
# 初始化一个二维访问数组vis，用于标记某个位置是否被访问过
vis = [[0 for _ in range(N)] for _ in range(N)]
 
 
def dfs(x, y, stk):
    u = len(stk)  # 获取当前堆栈的大小
    if u == 4:  # 如果堆栈大小为4，标记堆栈中所有位置为已访问，并终止搜索
        for i in range(4):
            # 元组，stk[i][0]表示第i个位置的x坐标，stk[i][1]表示第i个位置的y坐标
            vis[stk[i][0]][stk[i][1]] = 1
        return
 
    for i in range(4):  # 循环遍历四个可能的方向
        tx = x + dx[i]  # 计算新的x位置
        ty = y + dy[i]  # 计算新的y位置
        # 检查新位置是否在边界内，堆栈大小是否小于目标字符串的长度，和新位置的字符是否匹配目标字符串的当前字符
        if 0 <= tx < n and 0 <= ty < m and u < len(ctgu) and s[tx][ty] == ctgu[u]:
            # 如果满足条件，将新位置元组(tx, ty)添加到堆栈中
            stk.append((tx, ty))
            dfs(tx, ty, stk)  # 递归调用DFS函数
            stk.pop()  # 回溯：从堆栈中弹出最后一个位置  返回的是地图坐标
 
 
n, m = map(int, input().split())  # 输入n和m的值
for i in range(n):
    s[i] = list(input())  # 将输入的字符串转换为字符列表，并赋值给s数组的对应行
for i in range(n):
    for j in range(m):
        stk = []  # 初始化一个空堆栈
        dfs(i, j, stk)  # 从位置(i, j)开始执行DFS
 
ans = 0  # 初始化答案变量为0
for i in range(n):
    for j in range(m):
        if vis[i][j]:  # 如果位置(i, j)被访问过，增加答案变量
            ans += 1
print(ans)  # 输出最终答案