PTA 寻宝图

用户10216580

发布于 2024-03-27 08:15:42

11100

代码可运行

文章被收录于专栏：一叶知秋一叶知秋

运行总次数：0

代码可运行

今天是PTA题库解法讲解的第十五天，今天我们要讲解寻宝图，题目如下：

解题代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int>f[N],st[N];
int cnt,sum;
bool flag;
int n,m;
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
void dfs(int x,int y)
{
    st[x][y] = true;
    if(f[x][y] > 1) flag = true;
    for(int i = 0;i < 4;i++)
    {
        int xx = x + dx[i],yy = y + dy[i];
        if(xx >= 1 && xx <= n&&yy >= 1&&yy <= m&&f[xx][yy]&&!st[xx][yy])
        {
            if(f[xx][yy] > 1) flag = true;
            dfs(xx,yy);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
    {
        f[i].push_back(0);
        st[i].push_back(0);
        for(int j = 1;j <= m;j++)
        {
            char c;
            cin>>c;
            f[i].push_back(c-'0');
            st[i].push_back(0);
        }
    }
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
        {
            if(f[i][j] && !st[i][j])
            {
                flag = false;
                sum++;
                dfs(i,j);
                if(flag) cnt++;
            }
        }
    cout<<sum<<" "<<cnt;
    return 0;
}

思路：

这段代码的目的是在一个由数字组成的网格上寻找由相连的非零数字组成的区域（这里称为“宝藏”），并且特别标记包含数字大于1的区域。代码的基本思路是使用深度优先搜索（DFS）遍历网格，对每个未被访问过的非零点执行DFS，以找到所有相连的区域。如果一个区域包含任何大于1的数字，则将其标记为特殊区域。最后，输出两个数：总的区域数和包含大于1的数字的区域数。

优化想法：

以下是一些潜在的优化方向：

空间复杂度优化：在当前的实现中，f和st使用了vector<int>的数组来存储网格和状态，这导致较高的空间复杂度。一个可能的优化是使用单个二维vector来存储网格状态，减少内存使用。
避免重复访问：在DFS中，对于已经访问过的点，你已经通过st[x][y]进行了标记以避免重复访问，这个做法是合适的，但在实际编码时可以考虑使用更加直观的数据结构，比如直接的二维vector<bool>来存储访问状态。
迭代而非递归：对于深度优先搜索，递归是一种自然且简单的实现方式，但在极端情况下可能会导致栈溢出。一种替代方法是使用迭代加栈的方式实现DFS，这样可以手动控制栈的大小，避免溢出。
更高效的数据结构：对于大型数据，使用动态数组（如std::vector）可能不是最高效的选择。考虑到n和m的最大值，可以使用固定大小的数组（如果问题描述中给出了上限），或者使用更高效的数据结构，如稀疏矩阵（如果大部分元素都是零）。
并行处理：如果输入网格很大，可以考虑将网格分割成几个部分，使用并行算法（例如OpenMP）来同时处理这些部分。这种方法可以显著减少运行时间，特别是在多核处理器上。
启发式搜索：虽然对于此问题DFS是一个直接的解决方案，但在某些情况下，根据具体问题特点使用启发式搜索算法（如A*搜索）可能更有效。