深度优先搜索例题

#include <iostream>
#include <vector>

//3 3 3
//. 1 1
//2 * .
//2 . .

int height, width;
int health;

bool CanWalk(int Y, int X, int health, 
    const std::vector<std::vector<char>>& puzzle, std::vector<std::vector<bool>>& isVisited)
{
    if (Y < 0 || Y >= height || X < 0 || X >= width) return false;
    if (isVisited[Y][X]) return false;
    if (puzzle[Y][X] == '*') return false;

    if (puzzle[Y][X] <= '9' && puzzle[Y][X] >= '0')
    {
        int healthCost = puzzle[Y][X] - '0'; // 假设字符是数字的字符
        if (health - healthCost <= 0) return false;
    }
    
    return true;
}

bool dfs(int startY, int startX, int endY, int endX, int health,
    const std::vector<std::vector<char>>& puzzle, std::vector<std::vector<bool>>& isVisited)
{
    if (startX == endX && startY == endY)
    {
        return true;
    }

    isVisited[startY][startX] = true;

    if (puzzle[startY][startX] <= '9' && puzzle[startY][startX] >= '0')
    {
        int healthCost = puzzle[startY][startX] - '0';
        health -= healthCost;
        //std::cout << health << std::endl;
    }

    if (CanWalk(startY + 1, startX, health, puzzle, isVisited))
    {
        if(dfs(startY + 1, startX, endY, endX, health, puzzle, isVisited)) return true;
    }
    if (CanWalk(startY - 1, startX, health, puzzle, isVisited))
    {
        if(dfs(startY - 1, startX, endY, endX, health, puzzle, isVisited)) return true;
    }
    if (CanWalk(startY, startX + 1, health, puzzle, isVisited))
    {
        if(dfs(startY, startX + 1, endY, endX, health, puzzle, isVisited)) return true;
    }
    if (CanWalk(startY, startX - 1, health, puzzle, isVisited))
    {
        if(dfs(startY, startX - 1, endY, endX, health, puzzle, isVisited)) return true;
    }

    health += puzzle[startY][startX] - '0';
    isVisited[startY][startX] = false;

    return false;
}

int main()
{
    std::cin >> height >> width >> health;
    std::vector<std::vector<char>> puzzle(height, std::vector<char>(width));
    std::vector<std::vector<bool>> isVisited(height, std::vector<bool>(width, false));

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            std::cin >> puzzle[i][j];
        }
    }

    // 目标位置需要根据你的需求设定
    bool result = dfs(0, 0, height - 1, width - 1, health, puzzle, isVisited);
    std::cout << result << std::endl;

    return 0;
}