刷题笔记合集🔗

问题描述

小兰生活在蓝鲸城，这座城市的道路都是方方正正的。每天上班时，她都需要从家里出发到公司，但是每天路上的障碍物分布都不一样。

地图由以下元素组成：

• "." — 表示空地，可以通行
• "*" — 表示路障，需要清除才能通行
• "S" — 表示小兰的家
• "T" — 表示公司

小兰每天上班时有两个限制：

1. 最多只能拐弯 次
2. 最多只能清除 个路障

请你帮小兰计算一下，她今天是否能到达公司。

输入格式

第一行输入两个整数 和 （），分别表示最多可以拐弯的次数和最多可以清除的路障数。

第二行输入两个整数 和 （），表示地图的行数和列数。

接下来 行，每行包含 个字符，表示地图。保证地图中有且仅有一个 S 和一个 T。

输出格式

如果小兰能够到达公司，输出 "YES"； 如果不能到达，输出 "NO"。

样例1

输入：

2 0
5 5
..S..
****.
T....
****.
.....

输出：

YES

样例2

输入：

1 2
5 5
.*S*.
*****
..*..
*****
T....

输出：

NO

题解

这是一个带有特殊限制条件的迷宫搜索问题。主要需要考虑以下几点：

1. 搜索策略：

• 使用深度优先搜索遍历所有可能路径
• 记录已访问位置避免重复搜索
• 需要回溯以尝试不同路径

2. 状态记录：

• 当前位置坐标
• 已使用的拐弯次数
• 已使用的破壁次数
• 当前移动方向

3. 限制条件：

• 拐弯次数不能超过
• 破壁次数不能超过
• 不能走出地图边界
• 不能重复访问同一位置

时间复杂度分析：最坏情况下需要遍历所有可能路径，每个位置最多被访问一次，总时间复杂度为 。

参考代码

• Python

def find_path(row, col, turns, walls, prev_dir, seen):
    if grid[row][col] == 'T':
        return True
        
    dirs = [(-1,0,'u'), (1,0,'d'), (0,-1,'l'), (0,1,'r')]
    
    for dr, dc, d in dirs:
        nr, nc = row + dr, col + dc
        
        if nr < 0 or nr >= n or nc < 0 or nc >= m:
            continue
            
        if (nr,nc) in seen:
            continue
            
        need_turn = prev_dir and prev_dir != d
        if need_turn and turns + 1 > max_t:
            continue
            
        need_break = grid[nr][nc] == '*'
        if need_break and walls + 1 > max_w:
            continue
            
        seen.add((nr,nc))
        
        if find_path(nr, nc, 
                  turns + (1 if need_turn else 0),
                  walls + (1 if need_break else 0),
                  d, seen):
            return True
            
        seen.remove((nr,nc))
        
    return False

max_t, max_w = map(int, input().split())
n, m = map(int, input().split())
grid = [input() fo