TopCoder SRM 796 : Div1 Medium ChristmasSnake

まーたポカミスする…。
https://community.topcoder.com/stat?c=problem_statement&pm=16719&rd=18432

問題

8*8のグリッド上で行われるいわゆるスネークゲームを考える。
80手以内でヘビの位置を頭とおしり反転せよ。

なお、初期状態は以下の条件を持つ：

• 外周部にはヘビは存在しない
• 初期状態で、ヘビの先頭位置のマスと連結する空きマスは過半数である。

解法

条件が地味に重要で、外周部28マスは空きマス確定なので、ヘビは自分の体に邪魔されることなく必ず外周部に到達できる。
そのため、まずはBFSで外周部に到達したら外周部を1周し、開始位置から外周部に至るルートを逆走してそのままお尻の初期位置まで行けばよい。

int D[8][8];
int from[8][8];

class ChristmasSnake {
	public:
	vector<string> nex(vector <string> game, char cmd) {
		vector <string> nex=game;
		int cy,cx;
		int y,x;
		char la='a';
		FOR(y,8) FOR(x,8) {
			if(game[y][x]>='a'&&game[y][x]<='z') la=max(la,game[y][x]);
			if(game[y][x]=='a') cy=y,cx=x;
		}
		FOR(y,8) FOR(x,8) {
			if(nex[y][x]==la) nex[y][x]='.';
			if(nex[y][x]>='a'&&nex[y][x]<la) nex[y][x]++;
		}
		if(cmd=='N') cy--;
		if(cmd=='S') cy++;
		if(cmd=='W') cx--;
		if(cmd=='E') cx++;
		nex[cy][cx]='a';
		return nex;
		
	}
	
	string turnAround(vector <string> S) {
		/*
		string C="WSSSSENNNNESEENNW";
		int y;
		FORR(c,C) {
			game=nex(game,c);
			FOR(y,8) cout<<game[y]<<endl;
			cout<<endl;
		}
		*/
		int y,x,sy,sx,i;
		queue<int> Q;
		char la='a';
		FOR(y,8) FOR(x,8) {
			D[y][x]=100;
			if(S[y][x]=='a') {
				D[y][x]=0;
				sy=y;
				sx=x;
				Q.push({y*8+x});
			}
			if(S[y][x]>='a'&&S[y][x]<='z') la=max(la,S[y][x]);
		}
		int cy,cx;
		while(Q.size()) {
			cy=Q.front()/8;
			cx=Q.front()%8;
			Q.pop();
			if(cy==0||cx==0||cy==7||cx==7) break;
			int i;
			FOR(i,4) {
				int d[4]={1,0,-1,0};
				int ty=cy+d[i];
				int tx=cx+d[i^1];
				if(S[ty][tx]=='.'&&D[ty][tx]>D[cy][cx]+1) {
					D[ty][tx]=D[cy][cx]+1;
					from[ty][tx]=cy*8+cx;
					Q.push(ty*8+tx);
				}
			}
		}
		string R,R2;
		cout<<cy<<cx<<endl;
		y=cy,x=cx;
		while(D[y][x]) {
			int ty=from[y][x]/8;
			int tx=from[y][x]%8;
			if(ty==y-1) R+='S',R2+='N';
			else if(ty==y+1) R+='N',R2+='S';
			else if(tx==x-1) R+='E',R2+='W';
			else if(tx==x+1) R+='W',R2+='E';
			y=ty;
			x=tx;
		}
		reverse(ALL(R));
		y=cy;
		x=cx;
		FOR(i,28) {
			if(y==0&&x<7) x++, R+='E';
			else if(x==7&&y<7) y++, R+='S';
			else if(y==7&&x>0) x--, R+='W';
			else y--,R+='N';
		}
		R+=R2;
		
		while(S[sy][sx]<la) {
			FOR(i,4) {
				int d[4]={1,0,-1,0};
				int ty=sy+d[i];
				int tx=sx+d[i^1];
				if(ty<0||ty>7||tx<0||tx>7) continue;
				if(S[ty][tx]==S[sy][sx]+1) {
					
					if(ty>sy) R+='S';
					if(ty<sy) R+='N';
					if(tx>sx) R+='E';
					if(tx<sx) R+='W';
					sy=ty;
					sx=tx;
					break;
				}
			}
		}
		
		
		
		return R;
		
	}
}

まとめ

アイデアは難しくないけど実装が面倒。