TopCoder SRM523 Div1Hard

問題

高々21*21の盤面が与えられる。各マスは'.'か、アルファベットが書かれている。アルファベットは21種類のうちどれかである。今、この盤面上で「パス」を考える。パスは、iマス目がi+1マス目に隣接している(1 <= i <= 20)ような21個の互いに異なるマスの組み合わせである。パスのうち、構成するマスに21種類のアルファベットがすべて現れるようなパスは何個あるか。

解法

まず、パスの定義に「互いに異なる」とあるが、これは無視してもよいことがわかる。なぜなら、同じマスを通ったら21種類のアルファベットが現れることなどありえないからである。
すると、11マス目を固定して、そこを起点とする長さ11のパスを考え、パス構成するアルファベットが（起点マス以外において）異なるような2つのパスを併合してやると、自然と求めるパスになっている。そのようなものを数えればよい。
これを数えるのは、起点からDFSをすればよい。考えうる場合の数は高々4 * 3^10 = 236196通りしかない（実際はもっと少ない）。併合は、この少なさを利用して適当にやるとできる。

コード

#include <cstdio>
#include <vector>
#include <string>

using namespace std;

class AlphabetPaths
{
	int W, H, in[23][23];
	bool visited[23][23];
public:

	int bits[236196], bLast;
	int tmp[1<<21];
	
	void visit(int p, int q, int mask, int rem)
	{
		if(in[p][q]==-1) return;
		if(mask & in[p][q]) return;
		mask |= in[p][q];
		rem--;
		
		if(rem==0){
			bits[bLast++] = mask;
			return;
		}
		
		visit(p-1, q, mask, rem);
		visit(p+1, q, mask, rem);
		visit(p, q-1, mask, rem);
		visit(p, q+1, mask, rem);
	}
	
	long long solve(int p, int q)
	{
		if(in[p][q]==-1) return 0;
		
		bLast = 0;
		visit(p, q, 0, 11);
		
		for(int i=0;i<bLast;i++) tmp[bits[i]]++;
		int xorMask = ((1<<21) - 1) ^ in[p][q];
		long long ret = 0;
		
		for(int i=0;i<bLast;i++){
			ret += (long long)tmp[bits[i]] * tmp[xorMask ^ bits[i]] * 2;
			tmp[bits[i]] = 0;
			tmp[xorMask ^ bits[i]] = 0;
		}
		
		return ret;
	}
	
	int conv(char c)
	{
		char tbl[] = "ABCDEFZHIKLMNOPQRSTVX";
		for(int i=0;i<21;i++) if(tbl[i]==c) return i;
		return -1;
	}
	
	long long count(vector<string> lt)
	{
		W = lt[0].size();
		H = lt.size();
		
		for(int i=0;i<H+2;i++)
			for(int j=0;j<W+2;j++){
				in[i][j] = -1;
				visited[i][j] = false;
			}
		
		for(int i=0;i<H;i++)
			for(int j=0;j<W;j++){
				if(lt[i][j]!='.') in[i+1][j+1] = 1 << conv(lt[i][j]);
			}
		
		for(int i=0;i<(1<<21);i++) tmp[i] = 0;
		
		long long ret = 0;
		for(int i=1;i<=H;i++){
			for(int j=1;j<=W;j++){
				ret += solve(i, j);
			}
		}
		
		return ret;
	}
};