P10294 Harvest Waterloo

zhenghbkh · 2024-04-07 13:47:27 · 题解

看到这么好的迷宫题居然没有DFS的题解，好耶 太可惜了！于是来发一篇。

题目解析

本题与普通的迷宫题并无太大区别，只要在移动后加上此时脚底下南瓜的价值即可。

AC（？）代码

#include <iostream>
#include <cstring>
#define MAXN 32020
using namespace std;

int r, c, fx, fy, ans = 0;
char m[MAXN][MAXN];
int dx[] = {0, 0, 0, 1, -1};
int dy[] = {0, 1, -1, 0, 0};
bool vis[MAXN][MAXN]; 

int w(char a)/*获取当前南瓜的价值*/{
    if (a == 'S') return 1;
    else if (a == 'M') return 5;
    else return 10;
} 

void dfs(int y, int x){
    for (int i = 1; i <= 4; ++i){
        if (vis[y+dy[i]][x+dx[i]] || m[y+dy[i]][x+dx[i]] == '*' || y+dy[i] == 0 || y+dy[i] == r + 1 || x+dx[i] == 0 || x+dx[i] == c+1)
            continue; // 边界 
        else {
            vis[y+dy[i]][x+dx[i]] = true; // 走过了就标记不再走，避免死循环
            ans += w(m[y+dy[i]][x+dx[i]]);
            dfs(y+dy[i], x+dx[i]);
        }
    }
    return ;
}

signed main(){
    cin >> r >> c;
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j)
            cin >> m[i][j];
    cin >> fy >> fx;
    ++fy; ++fx;
    // read
    dfs(fy, fx);
    // work
    cout << ans;
    // write
    return 0;
}

好的以一种奇怪的方式爆0了

为什么呢？我们不难发现：当出发点周围都是干草时，农夫他出不去，也就意味着他走不回起点。所以DFS前要特判这种情况。

真正的AC代码

#include <iostream>
#include <cstring>
#define MAXN 1010
using namespace std;

int r, c, fx, fy, ans = 0;
char m[MAXN][MAXN];
int dx[] = {0, 0, 0, 1, -1};
int dy[] = {0, 1, -1, 0, 0};
bool vis[MAXN][MAXN];

void init(){
    for (int i = 1; i <= r; ++i) m[i][c+1] = m[i][0] = '*';
    for (int j = 1; j <= c; ++j) m[r+1][j] = m[0][j] = '*';
    return ;
}

int w(char a){
    if (a == 'S') return 1;
    else if (a == 'M') return 5;
    else return 10;
} 

void dfs(int y, int x){
    for (int i = 1; i <= 4; ++i){
        if (vis[y+dy[i]][x+dx[i]] || m[y+dy[i]][x+dx[i]] == '*' || y+dy[i] == 0 || y+dy[i] == r + 1 || x+dx[i] == 0 || x+dx[i] == c+1)
            continue; // 边界 
        else {
            vis[y+dy[i]][x+dx[i]] = true;
            ans += w(m[y+dy[i]][x+dx[i]]);
            dfs(y+dy[i], x+dx[i]);
        }
    }
    return ;
}

signed main(){
    cin >> r >> c;
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j)
            cin >> m[i][j];
    cin >> fy >> fx;
    ++fy; ++fx;
    // read
    init();
    if (m[fy+1][fx] == '*' && m[fy][fx+1] == '*' && m[fy][fx-1] == '*' && m[fy-1][fx] == '*') 
        ans = w(m[fy][fx]);
    else 
        dfs(fy, fx);
    // work
    cout << ans;
    // write
    return 0;
}

终于AC了！