Waiting ten thousand years for Love 时间的问题

Question

Problem Description
It was ten thousand years, after Demon Lemon caught Yifenfei’s love. In order to revenge and save his love, Yifenfei have been practising sword all day long and his Kongfu skills becomes so powerful that he can kill Demon Lemon immediately. Recently, Yifenfei have found Lemon’s castle, and now he is going to kill Lemon. At the same time, hearing about the terrible news, Demon Lemon is now preparing for escaping...

Now Yifenfei has got the map of the castle.
Here are all symbols of the map:
Only one ‘Y’ Indicates the start position of Yifenfei.
Only one ‘L’ Indicates the position of Demon Lemon.
‘.’ Indicate the road that Yifenfei can walk on it, or fly over it.
‘#’ Indicate the wall that Yifenfei can not walk or flay through it.
‘@’ Indicate the trap that Yifenfei can not walk on it, but can fly over it.

Yifenfei can walk or fly to one of up, down, left or right four directions each step, walk costs him 2 seconds per step, fly costs him 1 second per step and 1 magic power. His magic power will not increased, and if his magic power is zero, he can not fly any more.

Now Yifenfei asks you for helping him kill Demon Lemon smoothly. At the same time, Demon Lemon will Leave the castle Atfer T seconds. If Yifenfei can’t kill Demon Lemon this time, he have to wait another ten thousand years.

Input
Lots of test cases, please process to end of file. In each test case, firstly will have four integers N, M, T, P(1 <= N, M, P <= 80, 1 <= T <= 100000), indicates the size of map N * M, the Lemon’s leaving time(after T seconds, Lemon will disappeared) and Yifenfei’s magic power. Then an N * M two-dimensional array follows indicates the map.

Output
For each test case, first Print a line “Case C:”, C indicates the case number. Then, if Yifenfei can kill Demon Lemon successfully, Print “Yes, Yifenfei will kill Lemon at T sec.”, T indicates the minimum seconds he must cost. Otherwise, Print ”Poor Yifenfei, he has to wait another ten thousand years.”

Sample Input
2 3 2 2
Y@L
###
2 3 4 1
Y@L
###
2 3 4 0
Y.L
###
2 3 3 0
Y.L
###

Sample Output
Case 1:
Yes, Yifenfei will kill Lemon at 2 sec.
Case 2:
Poor Yifenfei, he has to wait another ten thousand years.
Case 3:
Yes, Yifenfei will kill Lemon at 4 sec.
Case 4:
Poor Yifenfei, he has to wait another ten thousand years.

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

To solve this problem, we can use Breadth First Search (BFS) algorithm to find the shortest path from Yifenfei to Demon Lemon on the map. Here is the approach to solve this problem:

1. We will start by finding the start position of Yifenfei and the position of Demon Lemon on the map.
2. We will create a 2D array to keep track of the minimum time required to reach each cell on the map.
3. We will use a queue to implement BFS. We will add the start position of Yifenfei to the queue.
4. While the queue is not empty, we will dequeue the front element and explore its neighboring cells. If a neighboring cell is a valid cell to move to (not a wall or trap), we will update the minimum time to reach that cell and add it to the queue.
5. We will repeat step 4 until we reach Demon Lemon or until we explore all possible paths.
6. If we reach Demon Lemon, we will output the minimum time required to reach it. If not, we will output "Poor Yifenfei, he has to wait another ten thousand years." Here is the sample code to solve this problem in C++:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int bfs(vector<vector<char>>& map, int N, int M, int T, int P) {
    vector<vector<int>> time(N, vector<int>(M, INT_MAX));
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    queue<pair<int, int>> q;
    pair<int, int> start, end;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 'Y') {
                start = {i, j};
            } else if (map[i][j] == 'L') {
                end = {i, j};
            }
        }
    }
    
    time[start.first][start.second] = 0;
    q.push(start);
    
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        
        for (auto& dir : directions) {
            int x = cur.first + dir.first;
            int y = cur.second + dir.second;
            
            if (x >= 0 && x < N && y >= 0 && y < M && map[x][y] != '#' && time[cur.first][cur.second] + 2 <= P) {
                int cost = map[x][y] == '@' ? 1 : 2;
                if (time[cur.first][cur.second] + cost < time[x][y]) {
                    time[x][y] = time[cur.first][cur.second] + cost;
                    q.push({x, y});
                }
            }
        }
    }
    
    if (time[end.first][end.second] <= T) {
        return time[end.first][end.second];
    } else {
        return -1;
    }
}
int main() {
    int N, M, T, P, caseNum = 1;
    
    while (cin >> N >> M >> T >> P) {
        vector<vector<char>> map(N, vector<char>(M));
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> map[i][j];
            }
        }
        
        int result = bfs(map, N, M, T, P);
        cout << "Case " << caseNum << ":" << endl;
        if (result != -1) {
            cout << "Yes, Yifenfei will kill Lemon at " << result << " sec." << endl;
        } else {
            cout << "Poor Yifenfei, he has to wait another ten thousand years." << endl;
        }
        
        caseNum++;
    }
    
    return 0;
}

The code reads the input for each test case, constructs the map, applies BFS to find the shortest path, and prints the output accordingly. This code should help you solve the problem in a structured and organized way.