SRM 417 medium CubeNets (practice)

2012-01-12

23:21 |

展開図が立方体になるかどうかを判定する問題。

dfs しながら立方体の底に１を貼りつけていく。回転させて再帰呼び出しして回転を戻す。

（当初戻すコードを入れてなくて入れてみたら通ったけどほんとは最初にこれで行くって思いついて検証してから書き始めなければいかんなぁ....）

int f(int x, int y, vector<string>& fig, VI& w) {
	//cout<<x<<" "<<y<<" "<<fig[y][x]<<endl;
	fig[y][x]='-';
	int dx[4]={-1, 1, 0, 0};
	int dy[4]={0, 0, -1, 1};
	int rot[4][6]={
		{2,3,1,0,4,5}, //left
		{3,2,0,1,4,5}, //right
		{5,4,2,3,0,1}, //up
		{4,5,2,3,1,0}, //down
	};
	if(w[0]) return 0;
	w[0]=1;
	if(accumulate(ALL(w), 0)==6) return 1;
	REP(i, 4) {
		int yy=y+dy[i];
		int xx=x+dx[i];
		VI nw(6);
		REP(j, 6) nw[rot[i][j]]=w[j];
		if(0<=yy && yy<fig.size() && 0<=xx && xx<fig[0].size() && fig[yy][xx]=='#') if(f(xx, yy, fig, nw)) return 1;
		REP(j, 6) w[j]=nw[rot[i][j]];  // ←最初入れてなかった
	}
	return 0;
}

class CubeNets {
	public:
	string isCubeNet(vector <string> fig) {
		VI w(6);
		REP(y, fig.size()) REP(x, fig[0].size()) if(fig[y][x]=='#') return f(x, y, fig, w) ? "YES":"NO";
	}