UVa 387

UVa 387

題目：俄羅斯方塊、七巧板；已知一些放塊，不能旋轉方塊，問能否拼成4x4的方形。

分析：搜索。dfs枚舉所有放塊，然後模擬所有可能擺放的情況，求解判斷即可。

說明：注意每塊拼圖都要用上╮(╯▽╰)╭。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>using namespace std;typedef struct _block
{int  row, column;int  occupy;char data[4][5];
}block;
block B[100];char square[4][5] = {0};int cover(int id, int r, int c)
{if (r+B[id].row > 4 || c+B[id].column > 4) return 0;for (int i = r; i < r+B[id].row; ++ i)for (int j = c; j < c+B[id].column; ++ j) {if (square[i][j] != 0 && B[id].data[i-r][j-c] != '0')return 0;if (B[id].data[i-r][j-c] != '0')square[i][j] = '1'+id;}return 1;
}int uncover(int id)
{for (int i = 0; i < 4; ++ i)for (int j = 0; j < 4; ++ j)if (square[i][j] == '1'+id)square[i][j] = 0;
}int dfs(int s, int n, int e)
{if (e <= 0) {for (int i = 0; i < 4; ++ i)puts(square[i]);return 1;}if (s >= n) return 0;for (int i = s; i < n; ++ i) {if (B[i].occupy > e) continue;for (int r = 0; r <= 4; ++ r)for (int c = 0; c <= 4; ++ c) {if (cover(i, r, c) && dfs(i+1, n, e-B[i].occupy))return 1;uncover(i);}}return 0;
}int main()
{int t, r, c, cases = 0;while (cin >> t && t) {int sum = 0;for (int k = 0; k < t; ++ k) {cin >> B[k].row >> B[k].column;B[k].occupy = 0;for (int i = 0; i < B[k].row; ++ i) for (int j = 0; j < B[k].column; ++ j) {cin >> B[k].data[i][j];if (B[k].data[i][j] == '1') {B[k].data[i][j] += k;B[k].occupy ++;}}sum += B[k].occupy;}if (cases ++) puts(""); memset(square, 0, sizeof(square));if (sum != 16 || !dfs(0, t, 16))puts("No solution possible"); }return 0;
}