Desafios de Programação no Verão de 2011 - Prova 03 - Equipe

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Nurikabe (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<cstring>

#define N 16
char tab[N][128];
int n,m;

int bx, by;
char btab[N][N];

void imprime() {
	for(int i = 0; i < n; i++) {
		printf("%s\n", tab[i]);
	}
}

int leva(int x, int y) {
	return m*x + y;
}

int tem_quadrado(int pos) {
	for(int i = 1; i < n; i++) {
		for(int j = 1; j < m; j++) {
			int qtd = 0;
			for(int ii = i-1; ii <= i; ii++) {
				for(int jj = j-1; jj <= j; jj++) {
					if(leva(ii,jj) < pos && tab[ii][jj] == '#') {
						qtd++;
					}
				}
			}
			if(qtd == 4) return 1;
		}
	}
	return 0;
}

int lbl[N][N];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int fora(int x, int y) {
	if(x < 0 || x >= n || y < 0 || y >= m) return 1;
	return 0;
}

void dfs_agua(int x, int y) {
	if(fora(x,y)) return;
	if(lbl[x][y]) return;
	if(tab[x][y] != '#') return;
	lbl[x][y] = 1;
	for(int i = 0; i < 4; i++) {
		dfs_agua( x + dx[i], y + dy[i] );
	}
}

int agua_conexa(int pos) {

	memset(lbl, 0, sizeof(lbl));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(tab[i][j] == '#') {
				dfs_agua(i,j);
				i = n;
				j = m;
			}
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(leva(i,j) < pos && tab[i][j] == '#' && !lbl[i][j]) return 0;
		}
	}
	return 1;
}

int cnt;
void dfs_ilha(int x, int y) {
	if(fora(x,y)) return;
	if(lbl[x][y]) return;
	if(tab[x][y] == '#') return;
	if(tab[x][y] >= '1') cnt++;
	lbl[x][y] = 1;
	for(int i = 0; i < 4; i++) {
		dfs_ilha( x + dx[i], y + dy[i] );
	}
}

int ilhas_conexas() {
	memset(lbl, 0, sizeof(lbl));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(tab[i][j] >= '1') {
				cnt = 0;
				dfs_ilha(i,j);
				if(cnt >= 2) return 1;
			}
		}
	}
	return 0;
}

void dfs_area(int x, int y) {
	if(fora(x,y)) return;
	if(lbl[x][y]) return;
	if(tab[x][y] == '#') return;
	cnt++;
	lbl[x][y] = 1;
	for(int i = 0; i < 4; i++) {
		dfs_area( x + dx[i], y + dy[i] );
	}
}

int POS;
int area_maior(int ou_igual) {
	memset(lbl, 0, sizeof(lbl));
	int tot = 0, livre = 0, livre2 = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(tab[i][j] != '#') {
				livre++;
			}
			if(leva(i,j) < POS) {
				if(tab[i][j] != '#') {
					livre2++;
				}
			} else {
				livre2++;
			}
			if(tab[i][j] >= '1') {
				tot += tab[i][j] - '0';
				cnt = 0;
				dfs_area(i,j);
				if(ou_igual) {
					if(cnt != tab[i][j] - '0') return 1;
				} else {
					if(cnt > tab[i][j] - '0') return 1;
				}
			}
		}
	}
	if(ou_igual && livre != tot) return 1;
	if(livre2 < tot) return 1; 

	return 0;
}

void dfs_area_pos(int x, int y, int pos) {
	if(fora(x,y)) return;
	if(lbl[x][y]) return;
	if(leva(x,y) < pos && tab[x][y] == '#') return;
	cnt++;
	lbl[x][y] = 1;
	for(int i = 0; i < 4; i++) {
		dfs_area_pos( x + dx[i], y + dy[i], pos );
	}
}

void dfs_conta_ilhas(int x, int y, int pos) {
	if(fora(x,y)) return;
	if(lbl[x][y]) return;
	if(leva(x,y) < pos && tab[x][y] == '#') return;
	if(tab[x][y] >= '1') cnt++;
	lbl[x][y] = 1;
	for(int i = 0; i < 4; i++) {
		dfs_conta_ilhas( x + dx[i], y + dy[i], pos );
	}


}

int ilha_vazia_ou_menor(int pos) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(tab[i][j] >= '1') {
				cnt = 0;
				memset(lbl, 0, sizeof(lbl));
				dfs_area_pos(i,j,pos);
				if(cnt < tab[i][j] - '0') return 1;
			}
			if(/*leva(i,j) < pos &&*/ tab[i][j] == '.') {
				cnt = 0;
				memset(lbl, 0, sizeof(lbl));
				dfs_conta_ilhas(i,j,pos);
				if(cnt == 0) return 1;
			}
		}
	}
	return 0;
}

int invalido(int x, int y) {
	int pos = leva(x,y);
	POS = pos;
	if(tem_quadrado(pos)) {
		return 1;
	}
	if(!agua_conexa(pos)) {
		return 1;
	}
	if(ilhas_conexas()) {
		return 1;
	}
	if(area_maior(0)) return 1;
	if(ilha_vazia_ou_menor(pos)) return 1;

	return 0;
}

int correto() {
	if(!area_maior(1)) return 1;
	return 0;
}

int resolve(int x, int y) {

	if(y == m) {
		if(resolve(x+1, 0)) return 1;
		return 0;
	}

	if(leva(x,y) > leva(bx, by)) {
		bx = x;
		by = y;
		for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
			btab[i][j] = tab[i][j];
		}
	}


	if(invalido(x,y)) {
		return 0;
	}
	if(x == n) {
		if(correto()) {
			imprime();
			return 1;
		} else {
			return 0;
		}
	}
	else if(y == m) {
		if(resolve(x+1, 0)) return 1;
		else return 0;
	} else {
		if(tab[x][y] == '#') {
			tab[x][y] = '.';
			if(resolve(x,y+1)) return 1;
			tab[x][y] = '#';
			if(resolve(x,y+1)) return 1;
		} else {
			if(resolve(x,y+1)) return 1;
		}
		return 0;
	}
}

int main() {
	int prim = 1;
	while(scanf("%d %d", &n, &m) == 2 && (n || m)) {
		if(!prim) printf("\n");
		prim = 0;
		for(int i = 0; i < n; i++) {
			scanf("%s", tab[i]);
			for(int j = 0; j < m; j++) {
				if(tab[i][j] == '.') tab[i][j] = '#';
			}
			//printf("%s\n", tab[i]);
		}
		bx = 0;
		by = 0;

		if(resolve(0,0) == 0) {
			printf("NOT : \n");
			imprime();	
			printf("BEST (%d,%d): \n", bx, by);
			for(int i = 0; i < n; i++) {
				printf("%s\n", btab[i]);
			}
		}
	}
	return 0;
}

Kakuro (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

#define NMAX 8

int m, n;
struct st {
	int down, right, val;
	char sep;
} A[NMAX][NMAX];

int aux[9] = { 2, 8, 3, 4, 9, 6, 5, 1, 7 };

int backtrack(int i, int j) {
	if (i == m) return 1;
	int in = i, jn = j + 1;
	if (jn == n) { in++; jn = 0; }
	if (A[i][j].sep != '.') return backtrack(in, jn);
	int sumup = 0, sumleft = 0, rsu, rsl;
	int label[10], lblup[10], lblright[10];
	memset(label, -1, sizeof(label));
	memset(lblup, -1, sizeof(lblup));
	memset(lblright, -1, sizeof(lblright));
	for (int k = i-1; rsu = A[k][j].down, A[k][j].sep == '.'; k--) {
		label[A[k][j].val] = lblup[A[k][j].val] = 0; sumup+= A[k][j].val; }
	for (int l = j-1; rsl = A[i][l].right, A[i][l].sep == '.'; l--) {
		label[A[i][l].val] = lblright[A[i][l].val] = 0; sumleft+= A[i][l].val; }

	int only = -1;
	if (i+1 == m || A[i+1][j].sep != '.') {
		only = rsu - sumup;
	}
	if (j+1 == n || A[i][j+1].sep != '.') {
		if (only != -1 && only != rsl - sumleft) {
			return 0;
		}
		only = rsl - sumleft;
	}
	if (only != -1) {
		A[i][j].val = only;
		return 1 <= only && only <= 9 && label[only] && backtrack(in, jn);
	} else {
		int missdown = 0, missright = 0;
		for (int k = i+1; k < m && A[k][j].sep == '.'; k++) { missdown++; }
		for (int l = j+1; l < n && A[i][l].sep == '.'; l++) { missright++; }

		int somapequenosup = 0, somapequenosright = 0, somagrandesup = 0, somagrandesright = 0;
		int auxdown = missdown, auxright = missright;
		for (int lb = 1; lb <= 9 && auxdown; lb++) {
			if (lblup[lb]) {
				somapequenosup+= lb;
				auxdown--;
			}
		}
		for (int lb = 1; lb <= 9 && auxright; lb++) {
			if (lblright[lb]) {
				somapequenosright+= lb;
				auxright--;
			}
		}
		if (auxdown || auxright) {
			return 0;
		}
		auxdown = missdown; auxright = missright;
		for (int lb = 9; lb >= 1 && auxdown; lb--) {
			if (lblup[lb]) {
				somagrandesup+= lb;
				auxdown--;
			}
		}
		for (int lb = 9; lb >= 1 && auxright; lb--) {
			if (lblright[lb]) {
				somagrandesright+= lb;
				auxright--;
			}
		}
		for (int x = 0; x < 9; x++) {
			int lb = aux[x];
			//for (int lb = 9; lb >= 1; lb--) {
			if (label[lb] && sumup+lb <= rsu && sumleft+lb <= rsl) {
				if (somapequenosup > rsu - sumup - lb) {
					continue;
				}
				if (somapequenosright > rsl - sumleft - lb) {
					continue;
				}
				if (somagrandesup < rsu - sumup - lb) {
					continue;
				}
				if (somagrandesright < rsl - sumleft - lb) {
					continue;
				}
				A[i][j].val = lb;
				if (backtrack(in, jn)) {
					return 1;
				}
			}
		}
	}
	return 0;
}

int main() {
	scanf("%d %d", &m, &n);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			char str[8];
			scanf("%s", str);
			A[i][j].down = str[0] == 'X' ? -1 : atoi(&str[0]);
			A[i][j].right = str[3] == 'X' ? -1 : atoi(&str[3]);
			A[i][j].sep = str[2] != '.' ? 'X' : '.';
		}
	}
	backtrack(0, 0);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (j != 0) {
				printf(" ");
			}
			if (A[i][j].sep == '.') {
				printf("%d", A[i][j].val);
			} else {
				printf("_");
			}
		}
		printf("\n");
	}
	return 0;
}

Sudoku (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define NMAX 9

int A[NMAX][NMAX];
int n, N;

int backtrack(int i, int j) {
	if (i == N) {
		return 1;
	}
	int in = i, jn = j+1;
	if (jn == N) {
		in++;
		jn = 0;
	}
	if (A[i][j] != 0) {
		return backtrack(in, jn);
	}
	int label[NMAX+1];
	memset(label, -1, sizeof(label));
	for (int k = 0; k < N; k++) {
		label[A[i][k]] = 0;
		label[A[k][j]] = 0;
	}
	int I = n * (i / n);
	int J = n * (j / n);
	for (int k = I; k < I + n; k++) {
		for (int l = J; l < J + n; l++) {
			label[A[k][l]] = 0;
		}
	}
	for (int k = 1; k <= N; k++) {
		if (label[k] == -1) {
			A[i][j] = k;
			if (backtrack(in, jn)) {
				return 1;
			}
			A[i][j] = 0;
		}
	}
	return 0;
}

int main() {
	for (int test = 0; scanf("%d", &n) != EOF; test++) {
		if (test != 0) {
			printf("\n");
		}
		N = n*n;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				scanf("%d", &A[i][j]);
			}
		}
		if (backtrack(0, 0)) {
			for (int i = 0; i < N; i++) {
				printf("%d", A[i][0]);
				for (int j = 1; j < N; j++) {
					printf(" %d", A[i][j]);
				}
				printf("\n");
			}
		} else {
			printf("NO SOLUTION\n");
		}
	}
	return 0;
}

Light Up (por [IME-USP] Isso é tudo pessoal)

#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include<cctype>
#include<cmath>
#include <sstream>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;

#define PB(x) push_back(x)
#define MP(x,y) make_pair((x),(y))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(),(a).end()
#define REP(x,a,b) for(int x = (a);x < (b);x++)
#define FOR(x,n) REP(x,0,n)
#define FOREVER while(1)
#define WATCH(x) cout << #x << " = " << (x)
#define FOREACH(i,x) for(__typeof(x.begin()) i = x.begin(); i != x.end(); ++i)

#ifdef DEBUG
#define D(X) X
#else
#define D(X)
#endif

typedef long long ll;
const int inf = (1<<29);
int N,M,B;
int val[8][8];
int lights[8][8];
int otimo;

struct node{
	int x,y;
};
vector<node> events[8][8];
int dx[] = {1,0,0,-1};
int dy[] = {0,1,-1,0};

int valid(int x,int y) {
	if(x < N && y < M && x >= 0 && y >= 0) return 1;
	return 0;
}

int lamps(int x,int y) {
	for(int d = 0; d < 4; d++) {
		for(int xx = x, yy = y; valid(xx,yy) && val[xx][yy] == -1; xx += dx[d], yy += dy[d]) {
			if(lights[xx][yy]) {
				return 1;
			}
		}
	}
	return 0;
}

int verifica(int x,int y,int coloquei) {
	for(int i = 0; i < events[x][y].size(); i++) {
		int xx = events[x][y][i].x;
		int yy = events[x][y][i].y;
		if(val[xx][yy] != -1) {
			int count = 0;
			for(int d = 0; d < 4; d++) {
				int xxx = xx + dx[d];
				int yyy = yy + dy[d];
				if(valid(xxx, yyy) && lights[xxx][yyy]) {
					count++;
				}
			}
			if(count != val[xx][yy]) {
//				printf("ERRO no %d %d por causa do %d %d\n", xx, yy,x,y);
				return 0;
			}
		} else {
			if(!coloquei && !lamps(xx,yy)) {
//				printf("ERRO no %d %d por causa do %d %d\n", xx, yy,x,y);
				return 0;
			}
		}
	}
	return 1;
}

void backtrack(int x,int y, int qtd) {
//	printf("%d %d\n", x, y);
	if(x == N) {
		otimo = min(otimo, qtd);
		return;
	}
	int xx = x,yy = y + 1;
	if(yy >= M) {
		xx = x + 1;
		yy = 0;
	}
	if(val[x][y] == -1 && lamps(x,y)) {
		if(verifica(x,y,0)) {
//			printf("indo para o %d %d\n", xx, yy);
			backtrack(xx,yy, qtd);
		}
	} else if(val[x][y] == -1) {
		if(verifica(x,y,0)) {
//			printf("indo para o %d %d\n", xx, yy);
			backtrack(xx,yy, qtd);
		}
		lights[x][y] = 1;
		if(verifica(x,y,1)) {
//			printf("indo para o %d %d ps coloquei lampada no %d %d\n", xx, yy, x, y);
			backtrack(xx,yy,qtd+1);
		}
		lights[x][y] = 0;
	} else {
		backtrack(xx,yy,qtd);
	}
}

int main(){
	while(scanf("%d %d", &N, &M) == 2 && N ) {
		scanf("%d", &B);
		memset(val, -1, sizeof(val));
		for(int i = 0; i < B; i++) {
			int x,y,v;
			scanf("%d %d %d", &x, &y, &v);
			x--;y--;
			val[x][y] = (v == -1 ? -2 : v);
		}
		int ok = 1;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				events[i][j].clear();
			}
		}
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(val[i][j] == -1) {
					int x = -1;
					int y = -1;
					for(int d = 0; d < 2 && x == -1; d++) {
						int xx = i + (d == 0 ? dx[d] : 0);
						int yy = j + (d == 0 ? dy[d] : 0);
						while(valid(xx,yy) && val[xx][yy] == -1) {
							x = xx;
							y = yy;
							if(d == 2) break;
							xx += dx[d];
							yy += dy[d];
						}
					}
					events[x][y].push_back((node) {i, j});
				} else if(val[i][j] != -2){
					if(valid(i+1,j) && val[i+1][j] == -1) {
						events[i+1][j].push_back((node) {i, j});
					} else if(valid(i,j+1) && val[i][j+1] == -1) {
						events[i][j+1].push_back((node) {i, j});
					} else if(valid(i,j-1) && val[i][j-1] == -1) {
						events[i][j-1].push_back((node) {i, j});
					} else if(valid(i-1,j) && val[i-1][j] == -1) {
						events[i-1][j].push_back((node) {i, j});
					} else if(val[i][j] != 0) {
						ok = 0;
					}
				}
			}
		}
		memset(lights, 0, sizeof(lights));
		otimo = inf;
		if(ok) backtrack(0,0,0);
		if(otimo == inf) printf("No solution\n"); else printf("%d\n", otimo);
	}
    return 0;
}

Número de flechas (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
#define NMAX 10
int n;
int A[NMAX][NMAX];
int I[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int J[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
string N[] = { "NW", "N", "NE", "E", "SE", "S", "SW", "W" };
inline void getposition(int idx, int *i, int *j) {
	int a = idx / n, b = idx % n;
	if (a == 0) {
		*i = 0;
		*j = 1 + b;
		return;
	}
	if (a == 3) {
		*i = n + 1;
		*j = n - b;
		return;
	}
	int x = (idx - n);
	*i = 1 + (x / 2);
	if (x % 2 == 0) {
		*j = 0;
	} else {
		*j = n + 1;
	}
	/*
	int a = idx / n, b = idx % n;
	switch (a) {
		case 0: *i = 0; *j = 1 + b; break;
		case 1: *i = 1 + b; *j = n + 1; break;
		case 2: *i = n + 1; *j = n - b; break;
		case 3: *i = n - b; *j = 0; break;
	}
	*/
}
int M[NMAX][NMAX][NMAX][NMAX];
inline int cankill(int i, int j, int dir) {
	if (i == 0 && (dir < 4 || dir == 7)) {
		return 0;
	}
	if (j == n+1 && dir >= 1 && dir <= 5) {
		return 0;
	}
	if (i == n+1 && dir >= 3) {
		return 0;
	}
	if (j == 0 && (dir < 2 || dir > 4)) {
		return 0;
	}
	int ii = I[dir], jj = J[dir];
	int tokill = 0;
	for (int inc = 1; ; inc++) {
		int k = i + inc * ii;
		int l = j + inc * jj;
		if (1 <= k && k <= n && 1 <= l && l <= n) {
			tokill++;
			if (A[k][l] <= 0 || M[i][j][k][l] < A[k][l]) return 0;
			if (M[i][j][k][l] == A[k][l]) {
				return 2;
			}
		} else break;
	}
	return tokill > 0;
}
inline void kill(int i, int j, int dir, int plus = -1) {
	int ii = I[dir], jj = J[dir];
	for (int inc = 1; ; inc++) {
		int k = i + inc * ii;
		int l = j + inc * jj;
		if (1 <= k && k <= n && 1 <= l && l <= n) A[k][l]+= plus;
		else break;
	}
}
inline void unkill(int i, int j, int dir) {
	kill(i, j, dir, 1);
}
inline int pre() {
	int tab[NMAX][NMAX];
	memset(tab, 0, sizeof(tab));
	for (int idx = 4*n - 1; idx >= 0; idx--) {
		int i, j;
		getposition(idx, &i, &j);
		for (int dir = 0; dir < 8; dir++) {
			int ii = I[dir], jj = J[dir];
			for (int inc = 1; ; inc++) {
				int k = i + inc * ii;
				int l = j + inc * jj;
				if (1 <= k && k <= n && 1 <= l && l <= n) {
					M[i][j][k][l] = ++tab[k][l];
				} else {
					break;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (tab[i][j] < A[i][j]) {
				return 0;
			}
		}
	}
	return 1;
}
inline int killedeveryone() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (A[i][j] != 0) {
				return 0;
			}
		}
	}
	return 1;
}
int backtrack(int idx) {
	if (idx == 4*n && killedeveryone())
		return 1;
	int i, j;
	getposition(idx, &i, &j);
	for (int d = 0; d < 8; d++) {
		int dir = d;
		int can = cankill(i, j, dir);
		if (can) {
			kill(i, j, dir);
			if (backtrack(idx+1)) {
				A[i][j] = dir;
				unkill(i, j, dir);
				return 1;
			}
			unkill(i, j, dir);
			if (can == 2) {
				break;
			}
		}
	}
	return 0;
}
int main() {
	for (int test = 1; scanf("%d", &n) && n; test++) {
		memset(A, -1, sizeof(A));
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				scanf("%d", &A[i][j]);
			}
		}
		printf("Instancia #%d:\n", test);
		if (pre() && backtrack(0)) {
			printf("  ");
			for (int j = 1; j <= n; j++) {
				printf(" %2s", N[A[0][j]].c_str());
			}
			printf("   ");
			printf("\n");
			for (int i = 1; i <= n; i++) {
				printf("%2s", N[A[i][0]].c_str());
				for (int j = 1; j <= n; j++) {
					printf(" %2d", A[i][j]);
				}
				printf(" %2s\n", N[A[i][n+1]].c_str());
			}
			printf("  ");
			for (int j = 1; j <= n; j++) {
				printf(" %2s", N[A[n+1][j]].c_str());
			}
			printf("   ");
			printf("\n");
		} else {
			printf("sem solucao\n");
		}
		printf("\n");
	}
	return 0;
}

FurnitureRobbery (por SUDO)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define fori(i, n) for ( int i = 0; i < (n); ++i )
#define forr(i, a, b) for ( int i = (a); i <= (b); ++i )
#define ford(i, a, b) for ( int i = (a); i >= (b); --i )
#define tr(it, a, b) for ( typeof(a) it = (a); it != (b); ++it )
#define all(x) (x).begin(),(x).end()
#define sz size()
#define pb push_back

#define TRACE(x...)
#define PRINT(x...) TRACE(printf(x))
#define WATCH(x) TRACE(cout << #x" = " << x << "\n")

template<class T> string a2s(T x) { ostringstream o; o << x; return o.str(); }
template<class T> T s2a(string s) { istringstream i(s); T x; i >> x; return x; }

const double EPS = 1e-9;
const int INF = 0x3F3F3F3F;

int cmpD( double x, double y = 0, double tol = EPS ) {
    return ( x <= y + tol ) ? ( x + tol < y ) ? -1 : 0 : 1;
}

string str(int n) {
	string ans = "";
	while (n--) ans += " ";
	return ans;
}

void print(vector <string> &v) {
	for (int i=0; i < v.size(); i++) {
		cout << v[i] << endl;
	}
}

string& vtos(vector <string> &v, string &ans) {
	ans = "";
	for (int i=0; i < v.size(); i++) {
		ans += v[i];
	}
	return ans;
}

int solve(vector <string> &plan) {
	int r = plan.size();
	int c = plan[0].length();
	int di[] = {-1,1,0,0};
	int dj[] = {0,0,-1,1};
	vector <char> chars;
	set <char> chars_set;
	string dumb;
	
	for (int i=0; i < r; i++) {
		for (int j=0; j < c; j++) {
			if (isalpha(plan[i][j]) && chars_set.find(plan[i][j]) == chars_set.end()) {
				chars_set.insert(plan[i][j]);
				chars.push_back(plan[i][j]);
			}
		}
	}
	
	set < string > table;
	queue < pair <vector<string>,int> > q;
	
	q.push(make_pair(plan,0));
	table.insert(vtos(plan,dumb));
	
	while (!q.empty()) {
		pair <vector<string>,int> p = q.front(); q.pop();
		vector <string> v = p.first;
		int steps = p.second;
		
		for (int j=0; j < c; j++) {
			if (v[0][j] == 'A') {
				return steps;
			}
		}
		
		for (int i=0; i < chars.size(); i++) {
			for (int k=0; k < 4; k++) {
				bool good = true;
				
				for (int ii=0; ii < r; ii++) {
					for (int jj=0; jj < c; jj++) {
						if (v[ii][jj] == chars[i]) {
							if (ii+di[k] < 0 || ii+di[k] >= r || jj+dj[k] < 0 || jj+dj[k] >= c || (v[ii+di[k]][jj+dj[k]] != chars[i] && v[ii+di[k]][jj+dj[k]] != '.')) {
								good = false;
								goto SKIP;
							}
						}
					}
				}
				
				SKIP:
				if (!good) continue;
				
				vector <string> aux(r,str(c));
				for (int ii=0; ii < r; ii++) {
					for (int jj=0; jj < c; jj++) {
						if (ii-di[k] >= 0 && ii-di[k] <= r-1 && jj-dj[k] >= 0 && jj-dj[k] <= c-1 && v[ii-di[k]][jj-dj[k]] == chars[i]) {
							aux[ii][jj] = chars[i];
						}
						else {
							if (v[ii][jj] == chars[i]) {
								aux[ii][jj] = '.';
							}
							else {
								aux[ii][jj] = v[ii][jj];
							}
						}
					}
				}
				
				if (table.find(vtos(aux,dumb)) == table.end()) {
					q.push(make_pair(aux,steps+1));
					table.insert(dumb);
				}
			}
		}
	}
	
	return -1;
}

int main() {
	int n;
	
	while (cin >> n && n) {
		vector <string> v(n);
	
		for (int i=0; i < n; i++) {
			cin >> v[i];
		}
	
		cout << solve(v) << endl;
	}
	
    return 0;
}

Harder Sokoban Problem (por [IME-USP] Isso é tudo pessoal)

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

struct X {
	int x,y;
};

int n;
char tab[64][64];
int dist[25][25][25][25];
pair< X, X > fila[25*25*25*25];
int ini,fim;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};

int empty(int x, int y) {
	if(x < 0 || x >= n || y < 0 || y >= n) return 0;
	return tab[x][y] == '.';
}

int empty(X a) {
	return empty(a.x, a.y);
}

X make_x(int x, int y) {
	X novo;
	novo.x = x;
	novo.y = y;
	return novo;
}

int igual(X a, X b) {
	return a.x == b.x && a.y == b.y;
}

int main() {
	while(scanf("%d", &n) == 1) {
		memset(dist,-1,sizeof(dist));
		for(int i = 0; i < n; i++) {
			scanf("%s", tab[i]);
		}
		ini = fim = 0;
		X star;
		for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
			if(tab[i][j] == '*') {
				star.x = i;
				star.y = j;
				tab[i][j] = '.';
			}
		}
		for(int i = 0; i < 4; i++) {
			int x = star.x + dx[i];
			int y = star.y + dy[i];
			if(empty(x,y)) {
				fila[fim++] = make_pair( make_x(x,y), star );
				dist[x][y][star.x][star.y] = 0;
			}
		}
		while(ini < fim) {
			pair< X , X > at = fila[ini++];
			X h,c;
			h = at.first;
			c = at.second;
			for(int i = 0; i < 4; i++) {
				X vai = make_x( h.x + dx[i], h.y + dy[i] );
				if( empty(vai) && !igual(vai, c) && dist[vai.x][vai.y][c.x][c.y] == -1) {
					dist[vai.x][vai.y][c.x][c.y] = dist[h.x][h.y][c.x][c.y] + 1;
					fila[fim++] = make_pair( vai, c );

				}

				if( empty(vai) && abs( h.x - c.x ) == 1  && abs(h.y - c.y) == 0) {
					if(  abs( vai.x - c.x ) == 2  && vai.y == c.y  && dist[vai.x][vai.y][h.x][h.y] == -1) {
						dist[vai.x][vai.y][h.x][h.y] = dist[h.x][h.y][c.x][c.y] + 1;
						fila[fim++] = make_pair( vai, h );
					}
				}
				if( empty(vai) && abs( h.x - c.x ) == 0  && abs(h.y - c.y) == 1) {
					if( abs( vai.y - c.y ) == 2 && vai.x == c.x && dist[vai.x][vai.y][h.x][h.y] == -1) {
						dist[vai.x][vai.y][h.x][h.y] = dist[h.x][h.y][c.x][c.y] + 1;
						fila[fim++] = make_pair( vai, h );
					}
				}
			}
		}

		int resp = 0;
		for(int a = 0; a < n; a++) {
			for(int b = 0; b < n; b++) {
				for(int c = 0; c < n; c++) {
					for(int d = 0; d < n; d++) {
						if( igual( make_x(c,d), star ) ) continue;
						resp = max(resp, dist[a][b][c][d]);
					}
				}
			}
		}
		printf("%d\n", resp);
	}
	return 0;
}