是什么使leetcode#695 Max Area Island溢出

Question

我在leetcode#695遇到了一些问题。我不明白为什么我的代码会出现溢出结果。这是我的c代码。我想请你帮我指出我犯的错误。谢谢。

问题：

给出了一个mxn二元矩阵网格。岛屿是一组1（代表陆地）以4个方向（水平或垂直）相连你可以假设网格的四个边缘都被水包围。

孤岛的面积是孤岛中值为1的单元格的数量。

返回网格中岛屿的最大面积。如果没有孤岛，则返回0

问题链接

输入是

1.0，0，0 0，0 0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，1，1，1，1，1，1，1，1，1，1，1，0，0，0，1，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0 0,0]，[0,0,0,0,0,0,0,0,1,1,0,0,0]]输出：6说明：答案不是11，因为孤岛必须4向连接。

以下是我的解决方案：

/*
 * @lc app=leetcode id=695 lang=cpp
 *
 * [695] Max Area of Island
 */

// @lc code=start
class Solution {
public:
    vector<vector<bool>> mark;
    
    int calculate(vector<vector<int>>& grid, int i, int j, int row,int col){
        
        int buf_up, buf_down, buf_left, buf_right = 0;
        cout<<"i="<<i<<";j="<<j<<endl;
        
        if(mark[i][j] == true) return 0;

        if(mark[i][j] == false){
            cout<<"into mark false\n";
            mark[i][j] = true;
            cout<<"mark["<<i<<"]["<<j<<"]="<<mark[i][j]<<"\n";
        }

        if(grid[i][j] == 0) return 0;

        int c_buffer = 1;
        cout<<"initial c_buffer="<<c_buffer<<endl;
        //up
        if((i-1)>=0 && grid[i-1][j] == 1 && mark[i-1][j] == false){
            cout <<"up" <<endl;
            cout<<"before buf_up="<<buf_up<<"" <<endl;
            buf_up = calculate(grid, i-1, j, row, col);
            cout<<"after buf_up="<<buf_up<<"" <<endl;
            //cout<<"buffer="<<buffer<<endl;
        }
        //down
        if((i+1)<row && grid[i+1][j] == 1 && mark[i+1][j] == false){
            cout <<"down" <<endl;
            
            cout<<"before buf_down="<<buf_down<<"" <<endl;
            buf_down = calculate(grid, i+1, j, row, col);
            cout<<"after buf_down="<<buf_down<<"" <<endl;
            //cout<<"buffer="<<buffer<<endl;
        }
        //left
        if((j-1)>=0 && grid[i][j-1] == 1 && mark[i][j-1] == false){
            cout <<"left" <<endl;
           
            cout<<"before bufbuf_left_up="<<buf_left<<"" <<endl;
            buf_left = calculate(grid, i, j-1, row, col);
            cout<<"after buf_left="<<buf_left<<"" <<endl;
            //cout<<"buffer="<<buffer<<endl;
        }
        //right
        if((j+1)<col && grid[i][j+1] == 1 && mark[i][j+1] == false){
            cout <<"right" <<endl;
            
            cout<<"before buf_right="<<buf_right<<"" <<endl;
            buf_right = calculate(grid, i, j+1, row, col);
            cout<<"after buf_right="<<buf_right<<"" <<endl;
            //cout<<"buffer="<<buffer<<endl;
        }
        cout<<buf_up <<"|"<< buf_down <<"|"<< buf_left <<"|"<< buf_right <<"\n";
        
        c_buffer = c_buffer+ buf_up + buf_down + buf_left + buf_right;
        cout<<"end c_buffer="<<c_buffer<<endl;
  
       
        return c_buffer;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int res = 0;
        int max = 0;
        int buffer = 0;
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<bool>> save(row, vector<bool>(col,false));
        mark = save;
        for(int i = 0; i< row; i++ ){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
                    
                    buffer = calculate(grid,i,j,row,col);
                    cout<<"final_buffer="<<buffer<<endl;
                    if(buffer>max){  
                        max=buffer;
                        
                    }
                }
            }

        }
        //[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]\n
        //[[0,1,1],[1,1,0]]\n
        return max;
    }
};
// @lc code=end

            

错误：

运行时错误
✘ 错误：第59行：字符59：运行时错误：有符号整数溢出：808925107 1610678760无法在类型“int”（solution.cpp）中表示
✘ 错误：第59行：字符59：运行时错误：有符号整数溢出：808925107 1610678760无法在类型“int”（solution.cpp）中表示摘要：UndefinedBehaviorSanitizer:undefined behavior prog_joined。cpp:68:59

我认为这意味着在某些方向上有溢出值。在我跟踪它们之后，它们没有进入任何方向条件，然后c_缓冲区变成了溢出值。

我的标准输出：

 i=0;j=2
into mark false
mark[0][2]=1
initial c_buffer=1
32765|4|0|0
end c_buffer=32770
final_buffer=32770
i=0;j=7
into mark false
mark[0][7]=1
initial c_buffer=1
down
before buf_down=0
i=1;j=7
into mark false
mark[1][7]=1
initial c_buffer=1
right
before buf_right=0
i=1;j=8
into mark false
mark[1][8]=1
initial c_buffer=1
right
before buf_right=0
i=1;j=9
into mark false
mark[1][9]=1
initial c_buffer=1
805338995|512|0|0
end c_buffer=805339508
after buf_right=805339508
805338995|256|0|805339508
end c_buffer=1610678760
after buf_right=1610678760
808924978|128|0|1610678760

我拒绝buf_up、buf_down、buf_left、buf_right的价值观808924978,128,0,1610678760。我不知道是什么原因造成了这个结果。谢谢你。

Answer 1

我稍微修改了你的代码，并在一开始添加了边界检查条件。问题在于你在边界上的一次检查导致溢出

// @lc code=start
class Solution {
public:
    vector<vector<bool>> mark;
    
    int calculate(vector<vector<int>>& grid, int i, int j, int row,int col){
        if (i < 0 || j < 0 || i >= row || j >= col || grid[i][j] == 0 || mark[i][j] == true)
            return 0;
        mark[i][j] = true;
        int buf_up, buf_down, buf_left, buf_right = 0;
        int c_buff = 1;
        buf_up = calculate(grid, i-1, j, row, col);
        buf_down = calculate(grid, i + 1, j, row, col);
        buf_left = calculate(grid, i, j - 1, row, col);
        buf_right = calculate(grid, i, j + 1, row , col);
        c_buff += buf_up + buf_down + buf_left + buf_right;
        return c_buff;
        
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int res = 0;
        int max = 0;
        int buffer = 0;
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<bool>> save(row, vector<bool>(col,false));
        mark = save;
        for(int i = 0; i< row; i++ ){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
                    
                    buffer = calculate(grid,i,j,row,col);
                    cout<<"final_buffer="<<buffer<<endl;
                    if(buffer>max){  
                        max=buffer;
                        
                    }
                }
            }

        }
        //[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]\n
        //[[0,1,1],[1,1,0]]\n
        return max;
    }
};
// @lc code=end

这是可以接受的，在进行任何操作之前，请尝试检查边界。