T1212 仙島求藥——dfs 剪枝

分析

此題需要剪枝才能過，不然逾時，多用了一個dis數組去記錄到達每個點最少經過次數，如果目前cnt>dis，或者cnt已經比已得到臨時答案大了，可以直接return；這種搜尋的思路比較簡單，和紅與黑差不多；最短路問題建議使用bfs，因為dfs重複的情況太多，容易逾時。

#include<bits/stdc++.h>

using namespace std;

int m, n;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char c[25][25];
int vis[25][25];
int dis[25][25];//到某個點最少經過點數
int ans = 100;

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(cnt, dis[x][y]);
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (!vis[xx][yy] && !(c[xx][yy] == '#' || c[xx][yy] == '@') && xx >= 1 && yy >= 1 && xx <= m && yy <= n) {
            vis[xx][yy] = 1;
            dfs(xx, yy, cnt + 1);
            vis[xx][yy] = 0;
        }
    }
}

int main() {
    cin.tie(nullptr);
    cin >> m >> n;
    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 != 100)
        cout << ans << endl;
    else
        cout << -1 << endl;
    return 0;
}