Cracking the coding interview--Q8.6

January 13, 2013
作者:Hawstein
出处:http://hawstein.com/posts/8.6.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.

译文:

实现图像处理软件中的“填充”函数,给定一块区域(可以不规则),一个种子点和一种新颜色, 填充这块区域,直到到达这块区域的边界(边界是用这种新颜色画的一条封闭曲线)

解答

两种思路,一种递归,一种迭代。基本上能递归的都能迭代, 只不过有时迭代版本不是太好写。如果我没有记错, 填充函数在计算机图像学的书里是会讲的。给你一个种子点和一个颜色, 从这个种子点开始去把这块区域都填充上这种颜色。我们可以从这个种子点开始着色, 然后递归调用本函数去给它的上,下,左,右四个点着色。 递归停止条件是碰到这个区域的边界(边界是一条同种颜色绘制的封闭曲线)。比如说, 我先用绿色画了一个圆形(或是其它任意形状),然后在这个形状中间再用绿色点击一下, 那么这块区域就被填充成绿色了。下面是代码:

bool paint_fill(color **screen, int m, int n, int x, int y, color c){
    if(x<0 || x>=m || y<0 || y>=n) return false;
    if(screen[x][y] == c) return false;
    else{
        screen[x][y] = c;
        paint_fill(screen, m, n, x-1, y, c);
        paint_fill(screen, m, n, x+1, y, c);
        paint_fill(screen, m, n, x, y-1, c);
        paint_fill(screen, m, n, x, y+1, c);
    }
    return true;
}

迭代版本也不难,用BFS即可。每次给一个点着色后,就把它周围四个点放入队列, 只要队列不为空,就一直处理。这里需要注意一点的是,如果遇到一个点已经是新颜色, (比如上面说的绿色),那么我就不用处理它而且不需要把它周围四个点入队。 如果不注意这点,那么填充色就会不顾边界直接把整张图片都填充成同一种颜色。 迭代版本的就不写了。以下是完整代码:

#include <iostream>
#include <cstdio>
using namespace std;

enum color{
    red, yellow, blue, green
};

bool paint_fill(color **screen, int m, int n, int x, int y, color c){
    if(x<0 || x>=m || y<0 || y>=n) return false;
    if(screen[x][y] == c) return false;
    else{
        screen[x][y] = c;
        paint_fill(screen, m, n, x-1, y, c);
        paint_fill(screen, m, n, x+1, y, c);
        paint_fill(screen, m, n, x, y-1, c);
        paint_fill(screen, m, n, x, y+1, c);
    }
    return true;
}
int main(){
    freopen("8.6.in", "r", stdin);
    int m, n;
    cin>>m>>n;
    color **screen = new color*[m];
    for(int i=0; i<m; ++i)
        screen[i] = new color[n];
    for(int i=0; i<m; ++i)
        for(int j=0; j<n; ++j){
            int t;
            cin>>t;
            screen[i][j]=(color)t;
        }
    
    // color screen[5][5] = {
    //     {red, green, green, blue, yellow},
    //     {green, red, yellow, green, green},
    //     {green, green, red, blue, green},
    //     {red, green, green, green, yellow},
    //     {red, yellow, red, blue, yellow}
    // };
    paint_fill(screen, 5, 5, 1, 2, green);
    for(int i=0; i<5; ++i){
        for(int j=0; j<5; ++j)
            cout<<screen[i][j]<<" ";
        cout<<endl;
    }
    fclose(stdin);
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview