codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <cstdlib> #include <cstring> #include <string> #include <iostream> #include <fstream> #include <vector> class PatchWorker { public: PatchWorker() : matrix_width_(0), matrix_height_(0), mark_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(); mark_map_ = new bool[in_data_.length()](); std::cout << "filename : " << filename << "\n"; std::cout << "matrix : " << matrix_width_ << " x " << matrix_height_ << "\n"; } ~PatchWorker() { delete[] mark_map_; } void run() { searchMatrix(); countMatrix(); } private: struct Pos { int x_; int y_; Pos(const int x, const int y) : x_(x), y_(y) {} }; std::string in_data_; std::vector<Pos> child_list_temp_; int matrix_width_; int matrix_height_; bool* mark_map_; int max_score_; std::vector<Pos> max_score_cells_; char getInData(const int x, const int y) { return in_data_.at(y * matrix_width_ + x); } bool getMark(const int x, const int y) { return mark_map_[y * matrix_width_ + x]; } void setMark(const int x, const int y) { mark_map_[y * matrix_width_ + x] = true; } void countMatrix() { int* count_map = new int[matrix_height_](); for (std::vector<Pos>::iterator it = max_score_cells_.begin() ; it != max_score_cells_.end(); it++) { count_map[it->y_] ++; } for (int y = 0; y < matrix_height_; y++) { std::cout << count_map[y] << "\n"; } } void searchMatrix() { max_score_ = 0; for (int y = 0; y < matrix_height_; y++) { for (int x = 0; x < matrix_width_; x++) { if (!getMark(x, y)) searchRootCell(x, y); } } } void searchRootCell(const int x, const int y) { const char data = getInData(x, y); child_list_temp_.clear(); searchCell(x, y, data); int score = child_list_temp_.size(); if (score > max_score_) { max_score_ = score; max_score_cells_.assign(child_list_temp_.begin(), child_list_temp_.end()); } else if (score == max_score_) { max_score_cells_.insert(max_score_cells_.end(), child_list_temp_.begin(), child_list_temp_.end()); } } void searchCell(const int x, const int y, const char data) { if (getMark(x, y)) return; if (data != getInData(x, y)) return; child_list_temp_.push_back(Pos(x, y)); setMark(x, y); if (x > 0) searchCell(x - 1, y, data); if (x < matrix_width_ - 1) searchCell(x + 1, y, data); if (y > 0) searchCell(x, y - 1, data); if (y < matrix_height_ - 1) searchCell(x, y + 1, data); } }; 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); }
Private
[
?
]
Run code
Submit