Created
January 18, 2017 12:09
-
-
Save mizuhara/e2ad99f5dc800c1d56ed91e7348942ec to your computer and use it in GitHub Desktop.
An answer of http://nabetani.sakura.ne.jp/hena/ordf01_twicel/
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <queue> | |
#include <regex> | |
#include <string> | |
#include <bitset> | |
#include <sstream> | |
#include <iostream> | |
#include <algorithm> | |
const int width = 8; | |
const int height = 8; | |
const std::string black = "1"; | |
const std::string white = "0"; | |
const std::string dummy_string = "-"; | |
struct Pos | |
{ | |
int x; | |
int y; | |
}; | |
std::vector<std::string> split(const std::string & src, const std::string & sep) | |
{ | |
std::vector<std::string> ret; | |
const auto reg = sep.empty() ? std::regex("(.{1})") : std::regex(sep); | |
const auto flag = sep.empty() ? 1 : -1; | |
std::copy(std::sregex_token_iterator(src.begin(), src.end(), reg, flag), std::sregex_token_iterator(), std::back_inserter(ret)); | |
return ret; | |
} | |
std::string hex_to_bin(const std::string & hex) | |
{ | |
unsigned long ul; | |
std::stringstream ss(hex); | |
ss >> std::hex >> ul; | |
return std::bitset<8>(ul).to_string(); | |
} | |
std::vector<std::string> make_mass(const std::string & src) | |
{ | |
std::vector<std::string> mass; | |
const auto s = split(src, "/"); | |
for(auto && chr : s) { | |
const auto bin = hex_to_bin(chr); | |
mass.push_back(bin); | |
} | |
return mass; | |
} | |
std::vector<Pos> next_pos(const Pos & p) | |
{ | |
const std::vector<Pos> np = { | |
{ p.x + 1, p.y }, | |
{ p.x - 1, p.y }, | |
{ p.x, p.y + 1 }, | |
{ p.x, p.y - 1 }, | |
}; | |
return np; | |
} | |
bool is_pos_valid(const Pos & p) | |
{ | |
return (0 <= p.x && p.x < width) && (0 <= p.y && p.y < height); | |
} | |
int count_of(const std::vector<std::string> & mass, const std::string & s) | |
{ | |
int count { 0 }; | |
auto m = mass; | |
for(int h = 0; h < height; ++h) { | |
for(int w = 0; w < width; ++w) { | |
int tmp { 1 }; | |
std::queue<Pos> q; | |
if(m[h].substr(w, 1) != s) { | |
continue; | |
} | |
q.push({ h, w }); | |
while(!q.empty()) { | |
const auto cp = q.front(); q.pop(); | |
m[cp.x].replace(cp.y, 1, dummy_string); | |
const auto nps = next_pos(cp); | |
for(auto np : nps) { | |
if(!is_pos_valid(np)) { | |
continue; | |
} | |
if(m[np.x].substr(np.y, 1) != s) { | |
continue; | |
} | |
m[cp.x].replace(cp.y, 1, dummy_string); | |
q.push(np); | |
++tmp; | |
} | |
} | |
if(tmp == 2) { | |
++count; | |
} | |
} | |
} | |
return count; | |
} | |
std::string solve(const std::string & src) | |
{ | |
const auto mass = make_mass(src); | |
const auto white_count = count_of(mass, white); | |
const auto black_count = count_of(mass, black); | |
return std::to_string(white_count) + "," + std::to_string(black_count); | |
} | |
void test(const std::string & src, const std::string & expected) | |
{ | |
const auto actual = solve(src); | |
std::cout << (actual == expected ? "OK" : "***NG***") << std::endl; | |
} | |
int main() | |
{ | |
/*0*/ test( "dc/bc/a7/59/03/d5/d4/ea", "2,3" ); | |
/*1*/ test( "ff/ff/ff/ff/ff/ff/ff/ff", "0,0" ); | |
/*2*/ test( "00/00/00/00/00/00/00/00", "0,0" ); | |
/*3*/ test( "cc/33/cc/33/cc/33/cc/33", "16,16" ); | |
/*4*/ test( "aa/aa/55/55/aa/aa/55/55", "16,16" ); | |
/*5*/ test( "ac/a3/5c/53/ca/3a/c5/35", "8,8" ); | |
/*6*/ test( "db/00/db/00/db/00/aa/aa", "0,13" ); | |
/*7*/ test( "24/24/db/24/24/db/24/24", "0,12" ); | |
/*8*/ test( "d7/d7/e9/f1/f7/de/60/56", "3,2" ); | |
/*9*/ test( "17/7d/64/9b/a5/39/53/a6", "2,2" ); | |
/*10*/ test( "bb/8f/18/fb/89/c2/c7/35", "1,2" ); | |
/*11*/ test( "6d/63/20/08/54/cd/32/4f", "2,2" ); | |
/*12*/ test( "a9/ca/cd/46/99/e6/f0/30", "2,2" ); | |
/*13*/ test( "5b/70/fd/45/e2/a1/ab/9a", "1,2" ); | |
/*14*/ test( "24/e4/a8/12/e1/a6/3f/f3", "2,1" ); | |
/*15*/ test( "79/32/2e/07/d5/10/e7/9d", "2,2" ); | |
/*16*/ test( "60/bc/ab/ec/1f/eb/63/2c", "4,2" ); | |
/*17*/ test( "a5/dd/92/4e/67/c6/dc/34", "6,1" ); | |
/*18*/ test( "aa/96/6d/67/d2/a8/ac/90", "3,2" ); | |
/*19*/ test( "95/72/7d/5c/47/dc/ef/99", "4,0" ); | |
/*20*/ test( "17/d6/6a/27/1f/25/26/b8", "2,1" ); | |
/*21*/ test( "f0/f3/76/c5/31/ca/6b/ae", "1,2" ); | |
/*22*/ test( "01/59/26/fa/8c/70/12/cd", "1,4" ); | |
/*23*/ test( "1a/c3/1f/0b/83/b6/81/0d", "0,5" ); | |
/*24*/ test( "4c/49/05/cf/54/bb/1f/da", "1,2" ); | |
/*25*/ test( "eb/7c/d5/09/2a/c2/14/6b", "0,7" ); | |
/*26*/ test( "b4/d3/4c/c4/ed/19/e8/63", "1,3" ); | |
/*27*/ test( "bd/bc/6d/60/9b/00/9a/32", "2,4" ); | |
/*28*/ test( "94/97/3f/e3/c7/06/15/c0", "2,2" ); | |
/*29*/ test( "5f/1d/67/16/b8/f7/0a/2a", "2,2" ); | |
/*30*/ test( "df/e6/f9/4f/59/e9/1f/ee", "3,0" ); | |
/*31*/ test( "5a/53/9a/9a/73/b4/37/07", "3,2" ); | |
/*32*/ test( "bd/87/7c/e7/c0/37/82/da", "2,3" ); | |
/*33*/ test( "3d/c0/13/ac/57/3d/15/78", "2,2" ); | |
/*34*/ test( "63/64/54/3a/40/28/4e/4e", "0,3" ); | |
/*35*/ test( "f6/81/c9/15/00/4c/a0/a8", "1,4" ); | |
/*36*/ test( "19/41/df/f8/e3/74/6b/9b", "4,2" ); | |
/*37*/ test( "d5/0b/dd/35/3b/d2/0b/6b", "1,5" ); | |
/*38*/ test( "08/b7/91/f3/6e/3c/74/a0", "0,0" ); | |
/*39*/ test( "b8/a8/b4/a6/93/2c/94/3f", "0,0" ); | |
/*40*/ test( "88/22/21/ee/dc/19/43/01", "0,0" ); | |
/*41*/ test( "e1/ee/35/bc/fc/00/8e/fe", "0,0" ); | |
/*42*/ test( "3c/42/63/5f/27/47/07/90", "0,0" ); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment