Click here to Skip to main content
15,889,867 members
Please Sign up or sign in to vote.
1.33/5 (3 votes)
See more:
Puzzle Description

A complete list of accepted languages is in the Code Submission Guidelines.

During the day you work at a high flying design company, but at night you troll the internet as a hacker valuable programmer that tends to contribute to open source. No one knows your dual identity and once in a while a coworker will challenge you to solve a random problem.

As you chat at lunch, a coworker mentions he found a large number of digital black and white photos. He asks you how many clicks it would take to turn all these photos white by only using the pixel fill tool in your image manipulation program. The pixel fill tool is a neat feature that turns an area of black pixels into white pixels with just the click of a mouse.

The hacker in you smart programmer you are inside starts to think, and you determine you can programmatically figure out the answer...

For the sake of simplicity, a black and white image is a matrix composed of X * Y values.
A 0 represents a black pixel and a 1 represents a white pixel.

The following is a 7x5 image with some white and some black pixels:

10001
10100
00000
00000
00111
00100
00100

With one click, the pixel fill tool turns each black pixel into a white one until there isn't a black pixel that can be reached from the previous pixel. A pixel is connected with another one in up to eight ways: north, south, east, west and the four diagonals.

The image above can be filled with whites pixel with just two clicks: First click:

11111
11111
11111
11111
11111
11100
11100

Second click:

11111
11111
11111
11111
11111
11111
11111
Posted
Updated 28-Nov-11 21:32pm
v4
Comments
TorstenH. 29-Nov-11 3:33am    
I had to take out the "hacker" in this. Hackers are a myth, they don't exist.
Nagy Vilmos 6-Dec-11 10:45am    
What? But ... but ... but ... I thought Neo was 'The One'
TorstenH. 6-Dec-11 11:00am    
no pics - so he does not exist. that's the rule.
Legor 29-Nov-11 7:39am    
Do your own homework

MINESWEEPER!

I love this quest.
Give us a sneak into your code when you've got some.

And present us your solution, we do not do homework. You can ask specific questions and we are delighted to help you, but we do not provide code in any form (...as we would have to be paid for that).
 
Share this answer
 
Comments
Sergey Alexandrovich Kryukov 29-Nov-11 4:05am    
Good response, my 5.
Well, sometimes I enjoy providing some code, but only if the question is interesting enough to me...
--SA
TorstenH. 29-Nov-11 5:56am    
yeah, because it doesn't tickle otherwise. Don't we all know that feeling...
This is a very boring problem, because there is no any strategy: an algorithm is apparent right after one understands the problem. You just need to pick first zero, actually perform flood fill following the rules and repeat until all zeros are gone. Count the number of such cycles.

Do you really hope that someone will volunteer to help you more than I just did with such a boring problem? As this question is marked "homework", you're supposed to have all this fun along. School gives you a chance to learn something, use it well. Some experience will never hurt. Now, time to get to work!

Good luck,
—SA
 
Share this answer
 
v2
I think of two strategies here:

1 distinct zero-regions count
A zero-region is a region of 8-way connected zeros. Its border is an 8-way connected one-region or the image border.
The number of clicks you need is the number of zero-regions that are not connected to each other.

For other images, another strategy could be faster:

2 multiple inversions
You can get all the black pixels by repeatedly pixel fill the middle pixel, black and white alternating.
The number of clicks you need is the highest number of "layers" that black and white pixels are stuffed into one another.
0010000100
1110000111
0000000000
0000000000
1110000111
0010000100
Here, you would first white the middle pixel, leaving four black corners. The black the middle, resulting in a completely black image. And finally white again.

That would be 3 runs compared to the 5 that would be necessary using the first strategy.

Process both and take the faster one.

Oh, and I can think of constellations where a combination would be fastest.
 
Share this answer
 
v2
Comments
TorstenH. 29-Nov-11 5:57am    
I don't know where the starter is at right now in school, but most times it's more about 2-dimensional arrays and the basics of OOP.
This is how I would solve this.
C++
#include <stdio.h>
#include <vector>
#include <fstream>
#include <sstream>
#include <iostream>
#include <deque>

typedef std::vector<std::vector xmlns:std="#unknown"><bool> > table_t;


class Solver {
public:
    Solver(int H, int W): _height(H),
        _width(W),
        T(H, std::vector<bool>(W)),
        num_of_clicks(0){
    }
    ~Solver() {
    }
    void ReadFile(std::ifstream &ifs){
        int row = 0, col = 0;
        std::string file_line;
        while( ifs.good() ) {
            std::getline(ifs,file_line);
            for ( std::string::const_iterator it =  file_line.begin(); it != file_line.end(); ++it) {
                if ( *it - '0' == 1 ) {
                    T[row][col++] = true;
                } else {
                    T[row][col++] = false;
                }               
            }
            col = 0;
            row++;        
        }
        ifs.close();  
    }
    void solve() {
        for ( int row = 0; row < _height; ++row) {
            for ( int col = 0; col < _width; ++col) {
                if ( T[row][col]  == true )
                    continue;
                neighbours.clear();
                num_of_clicks++;
                neighbours.push_back(std::make_pair(row,col));
                while ( !neighbours.empty()) {
                    std::pair<int,int> elem = neighbours.front();
                    neighbours.pop_front();

                    int R = elem.first;
                    int C = elem.second;                    

                    west       (R, C);
                    east       (R, C);
                    north      (R, C);
                    south      (R, C);
                    north_west (R, C);
                    south_west (R, C);
                    south_east (R, C);
                    north_east (R, C);
                }
            } // colum loop ends here
        } // row loop ends here
        std::cout << num_of_clicks << std::endl;
    }
private:
    int _height;
    int _width;
    table_t T;
    std::deque<std::pair><int,int> > neighbours;
    int num_of_clicks;

    void west(int row, int col) {
        if ( col - 1 >= 0 && T[row][col - 1 ]  == false ) {
            T[row][col - 1 ]  = true;
            neighbours.push_back(std::make_pair(row, col - 1));
        }
    }

    void east(int row, int col) {
        if ( col + 1 < _width && T[row][col + 1 ] == false ) {
            T[row][col + 1 ] = true; 
            neighbours.push_back(std::make_pair(row, col + 1));
        }
    }

    void north(int row, int col) {
        if ( row - 1 >= 0 && T[row - 1][col] == false ) {
            T[row - 1][col] = true;
            neighbours.push_back(std::make_pair(row - 1, col));
        }
    }

    void south(int row, int col) {
        if ( row + 1 < _height && T[row + 1][col] == false ) {
            T[row + 1][col]= true;
            neighbours.push_back(std::make_pair(row + 1, col ));
        }
    }

    void north_west(int row, int col) {
        if (row - 1 >= 0 && col - 1 >= 0 &&
            T[row - 1][col - 1] == false ) {
                T[row - 1][col - 1] = true;
                neighbours.push_back(std::make_pair(row - 1, col -  1));
        }
    }

    void south_west(int row, int col) {
        if ( row + 1 < _height && col - 1 >= 0 &&
            T[row + 1][ col - 1] == false) {
                T[row + 1][ col - 1] = true;
                neighbours.push_back(std::make_pair(row + 1, col - 1));
        }
    }

    void south_east(int row, int col) {
        if ( row + 1 < _height && col + 1 < _width &&
            T[row + 1][col + 1] == false ){
                T[row + 1][col + 1] = true;
                neighbours.push_back(std::make_pair(row + 1, col + 1));
        }
    }

    void north_east(int row, int col) {
        if ( row - 1 >= 0 && col + 1 < _width &&
            T[row - 1][col + 1] == false ) {
                T[row - 1][col + 1] = true;
                neighbours.push_back(std::make_pair(row - 1, col + 1 ));
           
        }
    }
};

int main ( int argc, char **argv) {
    int H = 0;
    int W = 0;
    std::ifstream input(argv[1]);
    if ( input.peek() == EOF ) {
        return 1;
    }
    // Read the first line.
    std::string file_line; 
    std::getline(input,file_line);
    std::istringstream iss;
    iss.clear();
    iss.str(file_line);
    // Get the height and width of the image.
    iss >> H >> W;
    Solver s(H,W);
    s.ReadFile(input);
    s.solve();

    return 0;
}


</std::pair></bool></bool></std::vector></deque></iostream></sstream></fstream></vector></stdio.h>
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900