U577123 宝箱 题解

Pilris_ · 2025-07-06 17:16:37 · 题解

首先介绍一下深搜(虽然大家可能都会) 深搜就是一条路走到黑，当遇到一个障碍时再返回去尝试其他的路径

思路介绍

先按照右下左上的顺序遍历 判断：如果该点为"."就把该点的星琼加起来与之前的星琼加起来,再与之前的星琼和作比较
如果比它小,那我们就可以把它存储起来再往下继续搜索 直到走到终点(n,m)
其实就是最短路径的变形

标程如下

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

int n,m;
char s[110][110];
int num[110][110];
int d[110][110],k;
int fx[5] = {0,0,1,0,-1};
int fy[5] = {0,1,0,-1,0};

void dfs(int x,int y,int k){
    for(int i = 1;i <= 4;i++){
        int tx = x + fx[i];
        int ty = y + fy[i];
        if(s[tx][ty] == '.' && k + num[tx][ty] < d[tx][ty]){  //如果可以走 把当前的和与之前的和进行比较
            d[tx][ty] = k + num[tx][ty]; //更新d的值
            dfs(tx,ty,k + num[tx][ty]);
        }
    }
}

signed main(){
    memset(d,0x3f,sizeof(d)); //初始化
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cin>>s[i][j];
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cin>>num[i][j];
        }
    }
    if(n == 1 && m == 1){ //为了给d赋值 若n和m均等1时无法给d赋值(其实可以在自定义函数中先给d赋值再递归)
        cout<<num[1][1];
        return 0;
    }
    dfs(1,1,num[1][1]);

    cout<<d[n][m]; //输出至少可得的星琼
    return 0;
}