时间戳

首页 > 解决方案 > 大型测试用例中 C++ dfs 问题中的小错误

c++ - 大型测试用例中 C++ dfs 问题中的小错误

问题描述

我正在解决一个关于 leetcode 的问题，我的答案通过了 123 个测试用例，其中一个失败了。我无法弄清楚我的问题，因为测试用例很大，而且我的解决方案适用于我能想到的每一个小测试用例。leetcode 的讨论部分没有帮助，所以我想在这里试试。

问题是：“给你一张二维整数网格形式的地图，其中 1 代表土地，0 代表水。

网格单元水平/垂直（不是对角线）连接。网格完全被水包围，并且只有一个岛（即一个或多个相连的陆地单元）。

岛上没有“湖泊”（里面的水与岛屿周围的水无关）。一个单元格是边长为 1 的正方形。网格是矩形，宽度和高度不超过 100。确定岛屿的周长。

example test case: [[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Output: 16

https://leetcode.com/problems/island-perimeter/

我的解决方案


    class Solution {
    public:

     bool dfs(unordered_set<string> & set, vector<vector<int>> &grid, int x,int y, int& count)
    {
        if(x>=grid.size()||y>=grid[0].size()||y<0||x<0) 
        {
            return false; // false means current coordinate is not an island piece
        }
        string loco=to_string(x)+to_string(y);
        if(grid[x][y]==0)
            return false;
        if(set.find(loco)!=set.end())
        {
            return true; 
        }

        set.insert(loco); //insert island piece to visited pieces
        int temp=4-(dfs(set,grid,x+1,y,count)+dfs(set,grid,x-1,y,count)+dfs(set,grid,x,y+1,count)+dfs(set,grid,x,y-1,count)); //subtract the number of adjecent island pieces
        count+=temp;
        return true;

    }
    int islandPerimeter(vector<vector<int>>& grid) {
        unordered_set<string>set;
        int count=0;
        for(int i=0 ;i <grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                if(grid[i][j]==1) //find the first piece of island and run DFS
                {
                    dfs(set,grid,i,j,count);
                    return count;
                }

            }
        }
        return count;
    }
};

我检查了 leetcode 的讨论部分，但大多数解决方案都是迭代的，没有像我那样使用 DFS。我试图了解我的解决方案存在什么问题。

失败的测试用例是：

[[0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0], 
[0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0], 
[0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,1,0,1,1,0], 
[0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,0,0,1,0], 
[0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,1,0], 
[0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], 
[0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], 
[0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0], 
[1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0], 
[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0], 
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0], 
[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], 
[0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], 
[0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0], 
[0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0], 
[0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0], 
[0,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0], 
[0,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,0,0,0], 
[0,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0],[0,0,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0]]

预期输出=128 我的输出= 125

标签： c++depth-first-search

解决方案

您正在string loco=to_string(x)+to_string(y);用作std::set. 显然， ifx = 11和y = 1then 的关键是111，就像 whenx = 1和一样y = 11，它会破坏你的算法。

首先，使用 astd::string作为设置键是一个不寻常的选择。我建议std::pair<int, int>改用。使用您自己的专用于此目的的类型 ( struct Coordinate { int x, y; };) 会更清晰，但需要一些额外的样板文件（即operator<) 才能使用std::set，而std::pair它是开箱即用的。

推荐阅读