UVA

UVA

题目大意：给出N块碎片，问能否拼成4＊4的图形

解题思路：暴利求解，先判断能否拼成4＊4，即当中的1是否足够16个，再进行dfs

#include<cstdio>
#include<cstring>
const int N = 20;
struct pieces{int row;int col;int shape[N][N];
};pieces p[N];int vis[4][4];
int n;bool dfs(int cur) {if(cur == n) {return true;	}for(int i = 0; i <= 4 - p[cur].row; i++) for(int j = 0; j <= 4 -p[cur].col; j++) {bool ok = true;for(int k = 0; k < p[cur].row; k++)for(int l = 0; l < p[cur].col; l++)if(vis[i+k][j+l] && p[cur].shape[k][l] ) {ok = false;	}else if(!vis[i+k][j+l] && p[cur].shape[k][l])vis[i+k][j+l] = cur+1;		if(ok && dfs(cur+1))return true;for(int k = 0; k < p[cur].row; k++)for(int l = 0; l < p[cur].col; l++)if(vis[i+k][j+l] == cur+1)vis[i+k][j+l] = 0;}return false;
}int main() {int r,c;char t;int sum ;int bo = 1;while(scanf("%d",&n) != EOF && n){if(bo)bo = 0;elseprintf("n");sum = 0;memset(vis,0,sizeof(vis));memset(goal,0,sizeof(goal));for(int i = 0; i < n; i++) {scanf("%d%dn",&(p[i].row),&(p[i].col));for(int j = 0; j < p[i].row; j++) {for(int k = 0; k < p[i].col; k++){t = getchar();	 int a = t - '0';if(a != 0) {p[i].shape[j][k] = i + 1;sum++;}elsep[i].shape[j][k] = 0;}getchar();}}if(sum == 16 && dfs(0))for(int i = 0; i < 4; i++) {for(int j = 0; j < 4; j++)printf("%d",vis[i][j]);printf("n");}elseprintf("No solution possiblen");}return 0;
}