これまた難しい問題だったけど、綺麗な解法を思い浮かんで気持ちよかった。
(問題概要)
立方体の展開図が文字列で与えられる。
立方体の展開図として正しいかどうか判断せよ。
(解法)
サイコロの展開図として考える。
展開図にそってサイコロを転がして、接地面の数字を割り当てていく。
このとき以下の矛盾がなければよい。
- 同じ数字が2箇所ある
- 同じ場所に2通りの数字の振り方がある
私のサイコロライブラリはゴリ押しなので汚いですがコード。
#include <cstdio>
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#include <queue>
#include <set>
#include <iostream>
#include <sstream>
using namespace std;
class CubeNets {
public:
string isCubeNet(vector <string> figure);
};
class Dice{
public:
enum direction{
UP = 0,
RIGHT = 1,
DOWN = 2,
LEFT = 3,
RRIGHT= 4,
RLEFT = 5
};
private:
static int next_top[7][7][6];
static int next_right[7][7][6];
static int front[7][7];
int _top;
int _right;
static void initDie(){
front[1][3] = 2; front[1][2] = 4; front[1][4] = 5; front[1][5] = 3;
front[2][1] = 3; front[2][3] = 6; front[2][4] = 1; front[2][6] = 4;
front[3][1] = 5; front[3][2] = 1; front[3][5] = 6; front[3][6] = 2;
for(int i = 4; i < 7; i++){
for(int j = 1; j < 7; j++){
if(i == j || i + j == 7) continue;
int t = 7 - i;
int l = 7 - j;
front[i][j] = front[t][l];
}
}
for(int t = 1; t < 7; t++){
for(int r = 1; r < 7; r++){
if(t == r || t + r == 7) continue;
next_top[t][r][UP] = front[t][r];
next_top[t][r][LEFT] = r;
next_top[t][r][RIGHT] = 7 - r;
next_top[t][r][DOWN] = 7 - front[t][r];
next_top[t][r][RRIGHT] = t;
next_top[t][r][RLEFT] = t;
next_right[t][r][UP] = r;
next_right[t][r][LEFT] = 7 - t;
next_right[t][r][RIGHT] = t;
next_right[t][r][DOWN] = r;
next_right[t][r][RRIGHT] = 7 - front[t][r];
next_right[t][r][RLEFT] = front[t][r];
}
}
}
static void init(){
static bool _init = false;
if(!_init){
initDie();
_init = true;
}
}
public:
Dice(int t = 1, int r = 3) : _top(t), _right(r) {
init();
}
int getTop() const{ return _top; }
int getRight() const{ return _right; }
int getButtom() const{ return 7 - _top; }
int getLeft() const{ return 7 - _right; }
int getFront() const{ return front[_top][_right]; }
int getBack() const{ return 7 - front[_top][_right]; }
void next(int dir){
int tmp = _top;
_top = next_top[_top][_right][dir];
_right = next_right[tmp][_right][dir];
}
void right() { next(RIGHT); }
void left() { next(LEFT); }
void up() { next(UP); }
void down() { next(DOWN); }
void rright(){ next(RRIGHT); }
void rleft() { next(RLEFT); }
static void forceInit(){ init(); }
static int nextTop(int t, int r, int d){
return next_top[t][r][d];
}
static int nextRight(int t, int r, int d){
return next_right[t][r][d];
}
};
int Dice::next_right[7][7][6] = {{{0}}};
int Dice::next_top[7][7][6] = {{{0}}};
int Dice::front[7][7] = {{0}};
bool solve(const vector<string> &f){
const int h = f.size();
const int w = f[0].size();
vector<vector<int> > g(h, vector<int>(w));
int sx, sy;
REP(i, h){
REP(j, w){
if(f[i][j] == '#'){
sx = j; sy = i;
goto proc;
}
}
}
proc:;
int cnt = 0;
typedef pair<int, pair<int, Dice> > data;
vector<int> use(7);
queue<data> q;
q.push(make_pair(sx, make_pair(sy, Dice())));
while(q.size()){
const data dt = q.front(); q.pop();
const int x = dt.first;
const int y = dt.second.first;
const Dice d = dt.second.second;
if(g[y][x] != 0){
if(d.getButtom() != g[y][x])
return false;
else
continue;
}else{
if(use[d.getButtom()]) return false;
g[y][x] = d.getButtom();
use[d.getButtom()] = 1;
cnt++;
}
if(ISIN(x, y - 1, w, h) && f[y - 1][x] == '#'){
Dice dd = d;
dd.up();
q.push(data(x, make_pair(y - 1, dd)));
}
if(ISIN(x, y + 1, w, h) && f[y + 1][x] == '#'){
Dice dd = d;
dd.down();
q.push(data(x, make_pair(y + 1, dd)));
}
if(ISIN(x - 1, y, w, h) && f[y][x - 1] == '#'){
Dice dd = d;
dd.left();
q.push(data(x - 1, make_pair(y, dd)));
}
if(ISIN(x + 1, y, w, h) && f[y][x + 1] == '#'){
Dice dd = d;
dd.right();
q.push(data(x + 1, make_pair(y, dd)));
}
}
return cnt == 6;
}
string CubeNets::isCubeNet(vector <string> figure){
return solve(figure) ? "YES" : "NO";
}