[USACO08FEB]Meteor Shower S & 素数环 & dp路径记录 ——搜索练习三篇

目录

 一.Meteor Shower S bfs

思路 

代码实现

二.素数环 Prime Ring Problem dfs回溯

 思路

代码实现

***三.挖地雷 记忆化搜索记录路径

 思路

代码实现

---

 一.Meteor Shower S

1P2895 [USACO08FEB]Meteor Shower S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路 

思路比较简单，但是细节很多的搜索题。

虽然题目很复杂，但是抽象出主干其实就是一些区域不能走，问到一个安全区域的最短路径，很容易想到bfs。

但是这题麻烦的地方就是，这些不能通过的区域会根据行走的步数（时间）改变。

所以需要提前做一个预处理，把哪些区域是安全的哪些区域在某个时间是不能走的标记出来。

所以想到用一个二维数组map存储地图，并初始化为-1也就是安全点，并根据每个区域会在某个时间t及t之后，不能通过，打上这个t的记号。

但是这里要注意某个区域能不能通过是看这个区域最早的陨石何时落下，所以要加个判断，防止后来的陨石覆盖先前的陨石。

预处理结束我们就得到了记录安全区域和每个地点何时不能通过的地图。

接下来可以进行，搜索了。

如果搜索的过程中，当前的步数（时间）>=这个格子不能通过的时间，则不能通过，反之，当前步数（时间）<这个各种不能通过的时间，说明可以通过。

代码实现

#include
#include
#include
#include
#include
#include
using namespace std;
int m;
struct node {//存储位置和时间的结构体
    int x, y;
    int t;
}per[50002];


int v1[] = { 1,-1,0,0 };//方向数组
int v2[] = { 0,0,1,-1 };
int used[400][400];//没有限定最大范围，数组开大一点
int map[400][400];
void bfs() {
    queueq;
    q.push({ 0,0,0 });
    while (!q.empty()) {
        node now = q.front(); q.pop();
        for (int j = 0; j < 4; j++) {
            int nx = now.x + v1[j], ny = now.y + v2[j];
            if (nx >= 0 && ny >= 0 && used[nx][ny] == 0 && (map[nx][ny] > now.t + 1 || map[nx][ny] == -1)) {
                used[nx][ny] == 1;
                q.push({ nx,ny,now.t + 1 });
                if (map[nx][ny] == -1)
                {
                    cout << now.t + 1;
                    exit(0);
                }
            }
        }
    }
    cout << -1;
}
int main() {
    ios::sync_with_stdio(false); cout.tie(NULL);
    cin >> m;
    memset(map, -1, sizeof(map));
    for (int j = 1; j <= m; j++) {
        int x, y, t;
        cin >> x >> y >> t;
        if (t < map[x][y] || map[x][y] == -1)
            map[x][y] = t;
        for (int i = 0; i < 4; i++)//预处理map数组
        {
            int nx = x + v1[i], ny = y + v2[i];
            if (nx >= 0 && ny >= 0 && (map[nx][ny] == -1 || t < map[nx][ny]))//防止后来的陨石覆盖前面的
                map[nx][ny] = t;
        }

    }
    bfs();

}

二.素数环 Prime Ring Problem

UVA524 素数环 Prime Ring Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 思路

其实是比较简单和常规的dfs回溯，不过训练课上提到了就写写，复习一下回溯。

比较基本的回溯思想，就是枚举每个位置是否合理，如果到某个程度整个序列无法继续枚举了，就说明之前的某个环节的枚举出了问题，返回上一层搜索，并回溯到上一层的状态。

对于这题，就是枚举每个环的位置能填什么数，并判断相邻位置是否合法（相加为质数），注意头部固定为1，尾部需要和头部结合。

代码实现

#include 
using namespace std;
int dp[100];
int used[100];//判断当前数字是否可用
int n;
int sum = 0;
void print() {

    for (int j = 1; j < n; j++) {
        cout << dp[j] << " ";
    }
    cout << dp[n] << endl;
}
int is_prime(int n) {
    for (int j = 2; j < n; j++) {
        if (n % j == 0)
            return 0;
    }
    return 1;
}
void dfs(int dep) {
    if (dep > n && is_prime(dp[n] + dp[1]) == 1) {
        print();
        return;
    }
    for (int j = 2; j <= n; j++) {
        {
            if (used[j] == 0 && is_prime(j + dp[dep - 1]) == 1) {
                dp[dep] = j;
                used[j] = 1;
                dfs(dep + 1);
                used[j] = 0;
            }
        }
    }
}
int main()
{
    while (cin >> n) {
        dp[1] = 1;
        sum++;
        if (sum >= 2)cout << endl;
        cout << "Case " << sum << ":" << endl;
        dfs(2);
    }
}

***三.挖地雷

P2196 [NOIP1996 提高组] 挖地雷 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 思路

这题也是我主要想发这篇博客的原因也是重点，只看题目其实不难，就是一个简单dp也没什么细节的地方，但是这是我第一次写的dp记录路径。

要输出最优路径，就麻烦了一些。

这里思路是，首先先写出dp的基本框架——

设num[i] 为第 i 个地窖的地雷数。

 dp[i] 为从第i个地窖开始挖，能得到的最大地雷数。

j  为从 i 开始,第 j 个地窖是可以向下挖的。

 i  < j < = n(因为不能回头）

则状态转移方程。

但是同时，我们还要记录当前的路径。

记录路径我们采用链式数组的思想，设路径数组为path[]

如果当前路径为i->j,则表示为path[i]=j。

如果路径为i->j->k，表示为i->path[i]->path[j]

最后想链表一样输出即可，具体细节见代码

代码实现

#include 
#include 
#include
using namespace std;
int num[100];
int f[100][100];//邻接矩阵
int dp[100000];//表示从第n个地窖开始能挖到的最多地雷
int n;
//记录搜索路线
vector< int> path(100);
int k = 0;
int dfs(int dep) {//p为当前搜索的起点
    int res = 0;
    int pos = 0;

    if (dp[dep] != 0)return dp[dep];
    for (int j = dep + 1; j <= n; j++) {
        if (f[dep][j] == 1) { //选出每个dp[i]中最大的
            int t = dfs(j);
            if (res < t) {
                res = t;
                // 不断更新当前地窖最大地雷的方向
                pos = j;
            }
        }
    }
    path[dep] = pos;//记录路径 dep->pos
    return dp[dep] = res + num[dep];//后面路线中最大的那个加上当前地窖的值
}
int main()
{

    cin >> n;
    path[0] = -1;
    for (int j = 1; j <= n; j++) {
        cin >> num[j];
        path[j] = -1;//初始化为-1，当路径点为-1说明到头了
    }
    for (int j = 1; j <= n; j++)
        for (int i = j + 1; i <= n; i++) {
            cin >> f[j][i];
        }
    int ans = 0;
    int pos = 0;
    for (int j = 1; j <= n; j++) {
        dp[j] = dfs(j);//寻求最值
        if (dp[j] > ans) {
            ans = dp[j];
            pos = j;
        }
    }
    while (pos != -1) {//输出坐标
        if (pos != 0)
            cout << pos << " ";
        pos = path[pos];
    }

    cout << endl;
    cout << ans;

}