T1214 鳴人和佐助——dfs、bfs

佐助被大蛇丸誘騙走了，鳴人在多少時間内能追上他呢？

分析

bfs

1. 迷宮問題，求最短時間，和 拯救行動 差不多，存在打怪獸可以通過的另外條件；但是此題打怪獸不需要另耗時間，是以第一次找到的終點就是最短時間，不需要優先隊列。
2. 需要注意：關于vis的标記問題；因為顯然到達 (x,y) 時如果查克拉分别剩餘 a,b 這兩種是不同的狀态，有可能導緻不同的結果，但是你隻會判斷第一次到達 (x,y) 的狀态，是以用二維數組标記并不能解決問題。如果後面到達時的查克拉數量(剩餘可用)大于之前到達的量則可以加入隊列（以免走了最前面的路打野怪消耗完查克拉最後到達不了終點）,關于是否走過的問題，不能用二維數組vis，要用三維數組vis 因為加上了查克拉的數量。比如走到相同的位置可能查克拉數量不一樣，這也算不同的走法。vis[x][y][t]表示在(x,y)點時，查克拉還有t;
3. int ckl = current.ckl;需要放在for(0-4)中，//目前這個隊頭，所能到達的每個點的ckl（所到達每個點都有ckl，在外面指派，就讓某一個點用光了）

#include<bits/stdc++.h>

using namespace std;
struct node {
    int x, y, time, ckl;
};
int m, n, t;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char c[205][205];
int ans = 100000;
int vis[205][205][15];
queue<node> q;

void bfs() {
    while (!q.empty()) {
        node current = q.front();
        q.pop();
        int x = current.x, y = current.y, time = current.time;//, ckl = current.ckl; 不能在這裡指派
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            int ckl = current.ckl;//目前這個隊頭，所能到達的每個點的ckl（所到達每個點都有ckl，在外面指派，就讓某一個點用光了）
            if (!vis[xx][yy][ckl] && xx >= 1 && yy >= 1 && xx <= m && yy <= n) {
                node no;
                if (c[xx][yy] == '*') {
                    //遇到終點是可以走的，然後在下次bfs進行答案的選取
                    vis[xx][yy][ckl] = 1;
                    no.x = xx, no.y = yy, no.time = time + 1, no.ckl = ckl;
                    q.push(no);
                } else {
                    if (ckl > 0) {
                        ckl--;
                        vis[xx][yy][ckl] = 1;
                        no.x = xx, no.y = yy, no.time = time + 1, no.ckl = ckl;
                        q.push(no);
                    }
                }
                if (c[xx][yy] == '+') {
                    ans = no.time;
                    return;
                }
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> m >> n >> t;
    int x, y;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; ++j) {
            cin >> c[i][j];
            if (c[i][j] == '@') {
                x = i, y = j;
            }
        }
    }
    vis[x][y][t] = 1;
    node start;
    start.x = x, start.y = y, start.time = 0, start.ckl = t;
    q.push(start);
    bfs();
    if (ans == 100000)
        cout << -1;
    else
        cout << ans;
    return 0;
}

           

dfs（TLE）

dfs一如既往的逾時，看網上有的剪枝太奇妙了，自己隻會簡單的剪枝

#include<bits/stdc++.h>

using namespace std;

int m, n, t;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char c[205][205];
int ans = 10000000;
int dis[205][205];
int vis[205][205];

void dfs(int x, int y, int cnt) {
    if (cnt >= ans || cnt > dis[x][y])
        return;
    if (c[x][y] == '+') {
        ans = min(ans, cnt);
        return;
    }
    dis[x][y] = min(dis[x][y], cnt);
    for (int i = 0; i < 4; ++i) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (!vis[xx][yy] && xx >= 1 && yy >= 1 && xx <= m && yy <= n) {
            if (c[xx][yy] == '*' || c[xx][yy] == '+') {
                //遇到終點是可以走的，然後在下次dfs進行答案的選取
                vis[xx][yy] = 1;
                dfs(xx, yy, cnt + 1);
                vis[xx][yy] = 0;
            } else {
                if (t > 0) {
                    vis[xx][yy] = 1;
                    t--;
                    dfs(xx, yy, cnt + 1);
                    vis[xx][yy] = 0;
                    t++;
                }
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> m >> n >> t;
    memset(dis, 0x3f3f3f3f, sizeof dis);
    int x, y;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; ++j) {
            cin >> c[i][j];
            if (c[i][j] == '@') {
                x = i, y = j;
            }
        }
    }
    vis[x][y] = 1;
    dfs(x, y, 0);
    if (ans == 10000000)
        cout << -1;
    else
        cout << ans;
    return 0;
}