正经题解｜迷宫之最少花费时间

【算法分析】

dfs，回溯，如果下一个点符合条件则继续递归，直到找到终点。

mp[][]  //迷宫
vis[][] //vis[x][y]标记点(x,y)是否已访问
DFS(int x, int y, int sum)  //当前正在访问的点是(x,y)
    if (x, y) 是终点 //边界
       走到终点 更新最短时间ans
       return    //返回
    vis[x][y] = true  //标记点(x,y)已访问
    for 点(x, y)的上下左右点(nx,ny)
        if(nx,ny)没越界&&(nx,ny)未访问&&(nx,ny)不是墙
			if 是怪兽
            DFS(nx,ny,sum + (mp[nx][ny] - '0') + 1)  //需要花费 1 分钟 + 消灭怪兽的时间 
            else 
            DFS(nx, ny, sum + 1);  // 空地需要花费 1 分钟
    回溯

【参考代码】

#include <iostream>
using namespace std;

const int N = 30;
char mp[N][N];  // 迷宫
int n, m, ans = 2e9;  // 行，列，最短时间 
int sx, sy, ex, ey;  // (sx, sy) 起点，(ex, ey) 终点 
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};  // 方向数组
bool vis[N][N];  // 标记数组 

bool in(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= m;
}

// 搜索所有可能路径，并维护一个最短时间 
void DFS(int x, int y, int sum) {  // 正在访问 (x, y)，所花时间为 sum 
	if(x == ex && y == ey) {  // 走到终点 
		if(sum < ans) ans = sum;  // 更新最短时间
		return;  // 到达递归边界，返回 
	}
	vis[x][y] = true;
	for(int i = 0; i < 4; i++) {
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		// 未越界 && 未访问 && 不是障碍物和墙 
		if(in(nx, ny) && !vis[nx][ny] && mp[nx][ny] != '#') {
			if(mp[nx][ny] >= '1' && mp[nx][ny] <= '9')
				DFS(nx, ny, sum + (mp[nx][ny] - '0') + 1);  // 需要花费 1 分钟 + 消灭怪兽的时间 
			else
				DFS(nx, ny, sum + 1);  // 空地需要花费 1 分钟
		}
	}
	vis[x][y] = false;  // 回溯 
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> mp[i][j];
			if(mp[i][j] == 'Z') sx = i, sy = j;  // 起点位置
			if(mp[i][j] == 'W') ex = i, ey = j;  // 终点位置 
		}
	}
	DFS(sx, sy, 0);  // 从起点出发，找到到达终点的最短时间（也有可能找不到）
	if(ans == 2e9) cout << "IMPOSSIBLE";  // 从起点无法到达终点
	else cout << ans; 
	return 0;
}

【时间复杂度】

$O(nm)$

【预计得分】

$100pts$