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

Question

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

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

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

岛上没有 "lakes"（岛内的水与岛周围的水没有相连）。一个格子是一个边长为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

Answer 1

您正在使用 string loco=to_string(x)+to_string(y); 作为 std::set 的密钥。显然，如果 x = 11 和 y = 1 则密钥是 111，就像 x = 1 和 y = 11 时一样，这会破坏您的算法。

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

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

Minor bug in C++ dfs question in a big test case

c++

depth-first-search