Problem: http://nabetani.sakura.ne.jp/hena/ordf01_twicel/ Implementation links: http://qiita.com/Nabetani/items/8e02ede04315b4eadd6d
I don't know much about Java, so I may be writing something strange, but I posted it without worrying about it.
import org.junit.Assert;
import org.junit.jupiter.api.Test;
public class TwinCell {
private static class Solver {
private class Searcher
{
int c=0;
int col;
Searcher( int x, int y)
{
col = color(x,y);
search( x, y );
}
void search( int x, int y )
{
if ( col != color(x,y) || ( attended[y] & (1<<x)) != 0 ){
return;
}
c+=1;
attended[y] |= 1<<x;
search( x+1, y );
search( x-1, y );
search( x, y+1 );
search( x, y-1 );
}
int size()
{
return c;
}
}
int[] bits;
int[] attended = new int[8];
static final int WX = 8;
static final int WY = 8;
public Solver(int[] _bits)
{
bits = _bits;
}
boolean onField( int x, int y)
{
return !( x<0 || WX<=x || y<0 || WY<=y );
}
private int color( int x, int y ){
if ( !onField( x, y )){
return -1;
}
return (bits[y] & (1<<x) )==0 ? 0 : 1;
}
public int[] solve() {
int[] r = new int[2];
for( int y=0 ; y<WY ; ++y ){
for( int x=0 ; x<WX ; ++x ){
if ( new Searcher( x, y ).size()==2 ){
++r[color(x,y)];
}
}
}
return r;
}
}
public String solve( String src )
{
String[] lines = src.split("\\/");
int[] bits = new int[lines.length];
for( int i =0 ; i<lines.length ; ++i ){
bits[i]=Integer.parseInt(lines[i], 16);
}
int[] wb = new Solver( bits ).solve();
return String.format( "%d,%d", wb[0], wb[1] );
}
void test( String src, String expected )
{
Assert.assertEquals( expected, solve( src ));
}
@Test
void runAllTests()
{
/*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" );
}
}
Unlike the case of ruby and C99 (http://qiita.com/Nabetani/items/7814edd97911a80946f1), I decided to count the number of squares in the depth-first search.
I tried using the in-class in-class for the first time in my life. I also tried using a rare inner class that is not static.
Recommended Posts