刷题笔记合集🔗

上班之路

问题描述

小毛生活在美丽的蓝鲸城，大马路都是方方正正，但是每天马路的封闭情况都不一样。
地图由以下元素组成：
1）"." — 空地，可以达到；
2）"*" — 路障，不可达到；
3）"S" — 小毛的家；
4）"T" — 公司。
其中我们会限制 小毛 拐弯的次数，同时 小毛 可以清除给定个数的路障，现在你的任务是计算 小毛 是否可以从家里出发到达公司。

输入格式

输入的第一行为两个整数 , （）， 代表可以拐弯的次数， 代表可以清除的路障个数。

输入的第二行为两个整数 , （），代表地图的大小。

接下来是 行包含 个字符的地图。 和 可能不一样大。

我们保证地图里有 S 和 T。

输出格式

输出是否可以从家里出发到达公司，是则输出 YES，不能则输出 NO。

样例输入

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

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

样例输出

YES

NO

数据范围

• 
• 
• 地图中仅包含 "."、"*"、"S" 和 "T" 四种字符
• 地图中一定包含 "S" 和 "T"

题解

这道题目本质上是一个带有特殊限制条件的迷宫搜索问题。小毛需要从起点S走到终点T，但有两个限制条件：

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

这个问题可以用深度优先搜索(DFS)来解决。我们需要在常规的DFS基础上，额外记录已经拐弯的次数和已经清除的路障数量。

在DFS过程中，我们需要维护以下状态信息：

• 当前位置的坐标(i, j)
• 已拐弯次数ut
• 已清除路障次数uc
• 当前移动方向lastDirect
• 已经访问过的位置集合path

算法思路：

1. 首先在地图中找到起点S的位置
2. 从S开始进行DFS搜索
3. 在DFS的每一步，尝试向四个方向(上、下、左、右)移动
4. 在移动时，需要判断：
   • 新位置是否在地图范围内
   • 新位置是否已被访问过
   • 如果需要拐弯，拐弯次数是否已用完
   • 如果遇到路障，清除路障次数是否已用完
5. 如果能到达终点T，返回YES，否则返回NO

关键点解析：

1. 判断拐弯：当前移动方向与上一次移动方向不同时，需要消耗一次拐弯机会
2. 判断清除路障：当遇到"*"时，需要消耗一次清除路障机会
3. 路径记录：使用集合存储已访问位置，避免重复访问
4. 回溯：如果当前路径不能到达终点，需要回溯，尝试其他路径

通过这种方法，我们可以找到所有可能的路径，并判断是否存在满足限制条件的路径能够从S到达T。

时间复杂度为O(4^(n*m))，因为在最坏情况下，我们可能需要尝试地图中每个位置的所有可能路径。但实际上，由于拐弯次数和清除路障次数的限制，以及已访问位置的记录，搜索空间会大大减小。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
t, c = map(int, input().split())
n, m = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(input())

# 四个方向：上、下、左、右
dirs = [(-1, 0, 'up'), (1, 0, 'down'), (0, -1, 'left'), (0, 1, 'right')]

def find_path():
    # 找到起点S
    start_x, start_y = -1, -1
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'S':
                start_x, start_y = i, j
                break
        if start_x != -1:
            break
            
    # DFS函数
    def dfs(x, y, turns, walls, last_dir, visited):
        # 到达终点
        if grid[x][y] == 'T':
            return True
            
        # 尝试四个方向
        for dx, dy, curr_dir in dirs:
            nx, ny = x + dx, y + dy
            
            # 检查边界
            if not (0 <= nx < n and 0 <= ny < m):
                continue
                
            # 检查是否已访问
            pos = f"{nx}-{ny}"
            if pos in visited:
                continue
                
            # 检查是否需要拐弯
            need_turn = False
            if last_dir and last_dir != curr_dir:
                if turns + 1 > t:  # 拐弯次数用完
                    continue
                need_turn = True
                
            # 检查是否需要清除路障
            need_wall = False
            if grid[nx][ny] == '*':
                if walls + 1 > c:  # 清除路障次数用完
                    continue
                need_wall = True
                
            # 标记访问
            visited.add(pos)
            
            # 递归搜索
            if dfs(nx, ny, 
                turns + (1 if need_turn else 0), 
                walls + (1 if need_wall else 0), 
                curr_dir, visited):
                return True
                
            # 回溯
            visited.remove(pos)
            
        return False
    
    # 从起点开始搜索
    return "YES" if dfs(start_x, start_y, 0, 0, None, {f"{start_x}-{start_y}"}) else "NO"

# 输出结果
print(find_path())

• Cpp

#include <bits/stdc++.h>
using namespace std;

int t, c, n, m;
vector<string> grid;

// 四个方向：上、下、左、右
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const string dirs[4] = {"up", "down"