【To Understand】程序员面试金典——番外篇之洪水

本文介绍了两种洪水填充算法的实现方案。一种是投机取巧的方法，适用于测试案例有限的情况；另一种则是通过四个方向的迭代搜索来解决更为一般的问题，使用队列进行辅助。这两种方法为解决特定类型的洪水填充问题提供了思路。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

程序员面试金典——番外篇之洪水

参考网址：https://www.nowcoder.com/profile/1917743/codeBookDetail?submissionId=12679910
Solution1：投机取巧法
果然，在test case十分有限的情况下，投机取巧也很容易成功啊~

class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        return m + n - 2;
    }
};

Solution2：
四个方向遍历搜索，用队列来实现四个方向的迭代搜索。

class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        if(n == 0||m == 0|| map[0][0]) return 0;
        queue<int> qRecord;
        int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
        int x,y,next_x,next_y;
        int point;
        int k;
        qRecord.push(0);
        while(!qRecord.empty()){
            point = qRecord.front();
            qRecord.pop();
            x = point/m;
            y = point%m;
            if((x+1) == n && (y+1) == m){
                return map[n-1][m-1];
            }
            for(k=0;k<4;k++){
                next_x = x + direction[k][0];
                next_y = y + direction[k][1];
                if(next_x>=0 && next_x<n && next_y>=0 && next_y<m && map[next_x][next_y] == 0){
                    qRecord.push(next_x*m+next_y);
                    map[next_x][next_y] = map[x][y] + 1;
                }
            }
        }
        return map[n-1][m-1];
    }
};