svn.filsa.org sketches

Rev

Blame | Last modification | View Log | RSS feed

#include <cstdlib>
#include <cstring>
#include <string>
#include <iostream>
#include <fstream>
#include <vector>

class PatchWorker {
public:
    PatchWorker() : matrix_width_(0), matrix_height_(0), score_map_(NULL) {}
   
    void init(const char* filename) {
        char buf[1024];
        std::ifstream ifs(filename, std::ios::in);
        while (!ifs.eof()) {
            ifs.getline(buf, sizeof(buf));
            std::size_t len = std::strlen(buf);
            if (len == 0) continue;
            else if (matrix_width_ == 0) matrix_width_ = len;
            else if (matrix_width_ != len) exit(EXIT_FAILURE);
           
            in_data_.append(buf);
            matrix_height_++;
        }
        ifs.close();
       
        score_map_ = new int[in_data_.length()]();
        std::memset(score_map_, 0, in_data_.length());
       
        std::cout << "filename : " << filename << "\n";
        std::cout << "matrix : " << matrix_width_ << " x " <<  matrix_height_ << "\n";
       
    }
   
    ~PatchWorker() {
        delete[] score_map_;
    }
   
    void run() {
        searchMatrix();
    }
   
private:
    std::string in_data_;
    int matrix_width_;
    int matrix_height_;
    int* score_map_;

    struct Pos {
        int x_;
        int y_;
        Pos(int x, int y) : x_(x), y_(y) {}
    };
   
    char getInData(const int x, const int y) {
        return in_data_.at(y * matrix_width_ + x);
    }
   
    int getScore(const int x, const int y) {
        return score_map_[y * matrix_width_ + x];
    }
   
    void setScore(const int x, const int y, int score) {
        score_map_[y * matrix_width_ + x] = score;
    }
   
    void searchMatrix() {
        int max_score = 0;
        std::vector<Pos> child_list;
        for (int y = 0; y < matrix_height_; y++) {
            for (int x = 0; x < matrix_width_; x++) {
                if (!getScore(x, y)) {
                    int score = searchRootCell(x, y, child_list);
                    if (score > max_score) max_score = score;
                }
            }
        }
       
        for (int y = 0; y < matrix_height_; y++) {
            int count = 0;
            for (int x = 0; x < matrix_width_; x++) {
                if (getScore(x, y) == max_score) count ++;
            }
            std::cout << count << "\n";
        }
    }
   
    int searchRootCell(const int x, const int y, std::vector<Pos>& child_list) {
        const char data = getInData(x, y);
       
        child_list.clear();
        searchCell(x, y, data, child_list);
       
        int score = child_list.size();
        for (std::vector<Pos>::iterator it = child_list.begin(); it != child_list.end(); it++) {
            setScore(it->x_, it->y_, score);
        }
       
        return score;
    }
   
    void searchCell(const int x, const int y, const char data, std::vector<Pos>& child_list) {
        if (x < 0 || x >= matrix_width_ || y < 0 || y >= matrix_height_) return;
        if (getScore(x, y)) return;
        if (data != getInData(x, y)) return;
        child_list.push_back(Pos(x, y));
        setScore(x, y, 1);
       
        searchCell(x - 1, y, data, child_list);
        searchCell(x + 1, y, data, child_list);
        searchCell(x, y - 1, data, child_list);
        searchCell(x, y + 1, data, child_list);
    }
   
};

int main(int argc, const char **argv) {
    if (argc == 0) exit(EXIT_FAILURE);
   
    PatchWorker patch_worker;
    patch_worker.init(argv[1]);
    patch_worker.run();
   
    exit(EXIT_SUCCESS);
}