7th Contest of Newbies, UVa-12399 : NumPuzz II

問題概要

3*3のmod10なライツアウトを解く。

解法

mod 2なライツアウトと同様に先頭の桁に関して全探索する。

acceptされたコード

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 1<<29;

int dy[] = {0, 0, 0, 1, -1}, dx[] = {0, 1, -1, 0, 0};
int tmp[3][3], ans[3][3], best_ans[3][3];
int board[3][3];
char buf[2000];

bool init(){
	gets(buf);
	bool f = true;
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			f &= (scanf("%d ", board[i] + j) == 1);
		}
	}

	return f;
}

void push(int y, int x){
	for(int k=0; k<5; k++){
		int ny = y + dy[k], nx = x + dx[k];
		if(0<=ny && ny<3 && 0<=nx && nx<3){
			tmp[ny][nx]--;
			if(tmp[ny][nx] < 0){
				tmp[ny][nx] += 10;
			}
		}
	}
}

void solve(){
	int len = INF;

	for(int top=0; top<1000; top++){
		memcpy(tmp, board, sizeof(board));
		memset(ans, 0, sizeof(ans));

		ans[0][0] = top/100;
		ans[0][1] = (top/10) % 10;
		ans[0][2] = top % 10;

		for(int x=0; x<3; x++){
			for(int i=0; i<ans[0][x]; i++){
				push(0, x);
			}
		}

		for(int y=1; y<3; y++){
			for(int x=0; x<3; x++){
				ans[y][x] = tmp[y-1][x];
				for(int i=0; i<ans[y][x]; i++){
					push(y, x);
				}
			}
		}

		if(tmp[2][0] == 0 && tmp[2][1] == 0 && tmp[2][2] == 0){
			int cnt = 0;
			for(int i=0; i<3; i++){
				for(int j=0; j<3; j++){
					cnt += ans[i][j];
				}
			}
			if(cnt < len){
				len = cnt;
				memcpy(best_ans, ans, sizeof(ans));
			}
		}
	}


	if(len == INF){
		puts("No solution.");
	}
	else{
		for(int i=0; i<3; i++){
			for(int j=0; j<3; j++){
				for(int k=0; k<best_ans[i][j]; k++){
					putchar('a' + (i*3 + j));
				}
			}
		}
		puts("");
	}
}

int main(){
	while(init()){
		solve();
	}

	return 0;
}