abc.txt

aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnn
bbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnnoo
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnn
bbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnnoo
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnn
bbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnnoo
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnn
bbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnnoo
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnn
bbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnnoo
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnn
bbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnnoo
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnn
bbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnnoo
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnn
bbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnnoo
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnn
bbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnnoo
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnn
bbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnnoo
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnn
bbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzzaabbccddeeffgghhiijjkkllmmnnoo

demo.txt

||||||||||||||||||||||............................++++++++++++++++++++++++++++++
||||||||||||||||||||............@@@@........++++++++++++++++++++++++++++++++++++
||||||||||||||||||..........@@@@@@@@........++++############++++$$$$$$$$$$$$++++
||%%%%%%%%%%%%%%..........@@@@@@@@&&&&&&&&&&##############******$$$$$$$$$$$$$$++
%%%%%%%%%%==%%..........@@@@@@@@&&&&&&&&&&&&&&############********$$$$$$------++
%%%%%%%%====............@@@@@@@@&&&&&&&&&&&&&&##;;######**********$$$$$$------++
%%%%%%====..............@@@@@@@@&&&&&&&&&&&&&&;;;;;;####************$$--------++
%%%%======..............@@@@@@&&&&&&&&&&&&&&&&;;;;;;;;**************$$----------
%%%%%%==..............@@@@@@&&&&&&&&&&&&&&&&;;;;;;;;;;**************$$$$$$------
%%%%%%======........@@@@@@&&&&&&&&&&&&&&&&;;;;;;;;;;;;>>************,,,,$$------
''%%%%%%%%%%%%%%%%@@@@@@&&&&&&))))!!!!;;;;;;;;;;;;;;;;>>************,,,,,,----~~
''''%%%%%%%%%%%%@@@@))))))))))))))!!!!;;;;;;;;;;;;>>>>>>>>**********,,,,,,--~~~~
''''''%%%%%%%%@@@@@@))))))))))))!!!!!!;;;;;;;;>>>>>>>>>>>>>>>>{{****,,,,,,~~~~~~
''''''%%%%%%%%@@@@@@@@!!!!!!!!))!!!!!!;;;;]]]]]]>>>>>>>>>>>>>>{{{{,,,,,,,,~~~~~~
''''''''%%%%^^@@@@@@!!!!!!!!!!!!!!!!!!]]]]]]]]]]>>>>>>>>>>>>>>{{{{,,,,,,////~~~~
''''''''^^^^^^^^!!!!!!!!!!!!!!!!!!!!]]]]]]]]]]>>>>>>{{{{{{>>>>>>{{//,,,,////~~~~
''''''^^^^^^^^^^((((((__!!!!!!!!!!!!]]]]]]]]]]>>>>>>{{{{{{>>>>>>{{//////////::::
''''''^^^^^^^^^^((((((____!!!!]]]]]]]]]]]]]]]]>>>><<<<{{{{>>>>>>{{//////////::::
''''''''^^^^^^^^^^((((________]]]]]]]]]]]]__]]>><<<<<<{{{{{{>>>>{{////////::::::
''''''''^^^^^^^^((((((((________]]]]]]]]__________<<<<{{{{{{{{{{{{::::::::::::::
''''''''''''((((((((((((((__________________[[[[__<<<<<<{{{{{{{{::::::::::::::::
''''''''''''((((((((((((((((____________[[[[[[______<<<<<<<<::::::::::::::::::::

FourColor.cc

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <queue>
#include <unistd.h>
#include <utility>
#include <vector>

typedef std::vector<std::vector<int>> Pixmap;

Pixmap ReadMap(std::FILE* file) {
    Pixmap map;
    int ch;
    do {
        std::vector<int> row;
        for(;;) {
            ch = fgetc(file);
            if(ch == EOF || ch == '\n') {
                break;
            }
            row.push_back(ch);
        }
        if(!row.empty()) {
            map.push_back(std::move(row));
        }
    } while(ch != EOF);
    return map;
}

int GetChar(int block) {
    return block & 0xff;
}

int GetColor(int block) {
    return block >> 8;
}

void InitScreen(Pixmap const& map) {
    for(size_t i = 0; i < map.size(); ++i) {
        std::putchar('\n');
    }
}

void PrintMap(Pixmap const& map) {
    std::printf("\033[%dA", map.size());
    for(auto const& line : map) {
        std::printf("\033[37m");
        for(int block : line) {
            std::printf("\033[4%dm%c", GetColor(block), block);
        }
        std::printf("\033[0m\n");
    }
    usleep(16000);
}

bool FloodFill(Pixmap& map, int y, int x, int color) {
    int ch = GetChar(map[y][x]);
    std::queue<std::pair<int, int>> queue;
    queue.push(std::make_pair(y, x));
    while(!queue.empty()) {
        auto const& coord = queue.front();
        y = coord.first;
        x = coord.second;
        queue.pop();
        if(y < 0) continue;
        if(x < 0) continue;
        if(y >= (int) map.size()) continue;
        if(x >= (int) map[y].size()) continue;
        int& block = map[y][x];
        if(GetChar(block) != ch) {
            if(GetColor(block) == color) {
                return false;
            }
            continue;
        }
        if(GetColor(block) == color) {
            continue;
        }
        block |= color << 8;
        queue.push(std::make_pair(y-1, x));
        queue.push(std::make_pair(y, x-1));
        queue.push(std::make_pair(y, x+1));
        queue.push(std::make_pair(y+1, x));
    }
    return true;
}

std::pair<int, int> FindUncolored(Pixmap const& map) {
    for(size_t i = 0; i < map.size(); ++i) {
        for(size_t j = 0; j < map.at(i).size(); ++j) {
            int block = map.at(i).at(j);
            if(GetChar(block) != ' ' && GetColor(block) == 0) {
                return std::make_pair((int) i, (int) j);
            }
        }
    }
    return std::make_pair(-1, -1);
}

Pixmap Search(Pixmap const& initial, bool isBFS) {
    std::deque<Pixmap> queue;
    queue.push_back(initial);
    bool first_generation = true;
    while(!queue.empty()) {
        Pixmap map;
        if(isBFS) {
            map = std::move(queue.front());
            queue.pop_front();
        } else {
            map = std::move(queue.back());
            queue.pop_back();
        }
        PrintMap(map);
        auto coord = FindUncolored(map);
        int y = coord.first;
        int x = coord.second;
        if(y != -1) {
            for(int color = 1; color <= 4; ++color) {
                Pixmap nextmap(map);
                if(FloodFill(nextmap, y, x, isBFS ? 5-color : color)) {
                    queue.push_back(std::move(nextmap));
                }
                if(isBFS && first_generation) break;
            }
        } else {
            PrintMap(map);
            return map;
        }
        first_generation = false;
    }
    return Pixmap();
}

int main(int argc, char *argv[]) {
    char const* mapfilename = "map.txt";
    if(argc > 1) {
        mapfilename = argv[1];
    }
    bool isBFS = false;
    if(argc > 2) {
        isBFS = std::strcmp(argv[2], "BFS") == 0 || std::strcmp(argv[2], "bfs") == 0;
    }

    std::printf("Opening map file: %s\n", mapfilename);
    std::printf("Using search strategy: %s\n", isBFS ? "BFS" : "DFS");
    FILE* mapfile = std::fopen(mapfilename, "r");
    if(!mapfile) {
        std::perror("Error");
        return 2;
    }
    Pixmap map = ReadMap(mapfile);
    std::fclose(mapfile);
    InitScreen(map);
    map = Search(map, isBFS);
    return map.empty();
}

map.txt

                                                                                 
               ++@@    ########$$$$                            ++++@@%%$$$$$$$$$$
               $$$$############$$$$                          ++++++%%%%%%$$$$$$$$
             $$$$$$############$$$$                          ++++%%%%%%%%$$$$$$$$
           $$$$$$$$##############++++++      ++++            ####@@%%%%%%%%$$$$$$
           $$$$$$################++++++++++++++++%%%%%%%%%%%%##@@++++@@%%%%$$$$$$
         $$$$####################++++++++++++++++%%%%%%%%%%%%++++++++++++++    $$
       $$$$######################++++++++++++++++%%%%%%%%%%  ++++++++++++++++    
     %%$$$$$$$$##################++++++++++++++++%%%%%%%%%%%%  ++++++++++++++++  
     %%$$$$$$++++##################++++++++++++++%%%%%%%%%%%%  @@++++++++++++++  
   %%%%$$$$$$$$++++++############$$$$@@%%++++++++%%%%%%%%%%%%%%  @@++++++++++++++
   $$$$$$$$$$$$++++++++########$$$$$$$$%%%%%%++++################  ++++++++++++++
   $$$$$$$$$$$$++++++++++####$$$$$$$$$$%%%%%%%%%%################    ++++++++++++
   $$$$$$$$$$$$++++++++++$$$$$$$$$$$$$$%%%%%%%%%%################    ++++++++$$$$
   $$$$$$$$$$$$++++++++++$$$$$$$$$$$$$$%%%%%%%%%%##############%%%%    $$$$$$$$$$
   ####$$$$$$$$++++++++++$$$$$$$$$$$$%%%%%%%%%%%%##############%%%%    $$$$$$$$$$
   ####++++++++++++%%$$$$$$$$$$$$$$$$%%%%%%%%%%################$$$$$$$$$$$$$$    
 ####$$$$++++++++%%%%%%$$############$$%%%%%%%%################$$$$$$$$          
     $$$$$$++++%%++++##++############$$%%%%%%%%++############$$$$$$$$$$##  ######
     $$%%$$####%%%%++##++############%%%%%%%%++++############$$$$$$$$$$##########
       %%++########++##++##########$$$$%%++++++++++##########$$$$$$$$$$$$$$####  
         ++######++++##++++######$$$$$$++++++++++++##########$$$$$$$$$$$$$$####  
         ++++              ####$$$$$$$$++++++++++++++##########$$$$$$$$$$####    
                                 $$$$$$++##%%%%%%%%%%%%%%$$$$%%%%%%##########    
                                 %%%%######%%%%%%%%%%%%%%$$$$%%%%%%%%####        
                                 %%%%######%%%%%%%%%%%%%%$$$$%%%%%%%%####        
                               %%%%%%######%%%%%%%%%%%%%%$$++%%%%%%%%##          
                                 %%######%%%%%%%%%%%%%%%%++++++++%%%%            
                                   ####%%%%%%%%%%%%%%%%%%++++++++++              
                                   ######%%%%%%%%%%%%%%%%++++++++++              
                                     $$$$%%$$$$%%%%%%%%%%++++++++++              
                                     $$$$$$$$$$%%%%%%%%%%++++++++++              
                                     $$$$$$$$$$%%%%%%%%####$$++++++++            
                                     $$$$$$$$$$$$##%%######$$++++%%%%  &&        
                                     $$$$$$$$$$############$$%%%%%%%%        $$  
                                   $$$$$$$$$$$$############%%$$%%%%%%        $$  
                                   $$$$$$$$$$$$########$$$$%%$$%%%%      $$$$$$  
                                   %%%%%%%%$$$$######$$$$$$%%%%%%        $$$$$$  
                                   %%%%%%%%%%++++++$$$$$$$$%%%%          $$$$    
                                     %%%%%%%%++++++++$$$$$$%%            $$$$    
                                     %%%%%%%%++++++++++$$$$%%          $$$$$$    
                                     %%%%%%%%++++++++####$$%%          $$$$      
                                       %%%%%%++++++######@@              $$      
                                       %%%%%%++##########@@                      
                                       %%%%%%##############                      
                                         ##########$$$$##                        
                                         ##############                          
                                         ############                            
                                           ####