題意：有一個由火柴棍組成的正方形網(wǎng)格，每條邊有n根火柴，共2n(n+1)根。從上到下、從左到右給各個火柴編號。現(xiàn)在拿走一下火柴，問剩下的火柴中，至少還要拿走多少根火柴才能破壞正方形。

分析：列舉每種可能，顯然是回溯，思想就是每次考慮一個沒有被破壞的正方形，都被破壞就退出并更新當(dāng)前最優(yōu)解，就是深度。這題難點就是如何表示正方形，先將所有正方形枚舉出來，將它的四條邊存入數(shù)組，而它邊的表示可以算出來。

作者代碼中有很多巧妙之處，細細體會收獲很大，比如正方形的邊存入。

#include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<iostream> #include<vector> #include<list> #include<set> using namespace std; const int maxn = 100;int n; int existedge[maxn]; int contain[maxn][maxn]; int cursize[maxn],fullsize[maxn]; int allsquare = 0; int curbest; inline int row_match(int x, int y) {return (2 * n + 1)*x + y; } inline int col_match(int x, int y) {return (2 * n + 1)*x + n+y; } void init() {int m,v;cin >> n>>m;for (int i = 0; i < 2 * n*(n + 1); i++)existedge[i] = 1;for (int i = 0; i < m; i++) {cin >> v;existedge[v-1] = 0;}memset(contain, 0, sizeof(contain));allsquare = 0;for (int i = 1; i <= n; i++) {//枚舉 邊的數(shù)量for (int x = 0; x <= n-i; x++) {for (int y = 0; y <= n-i; y++) {cursize[allsquare] = 0;fullsize[allsquare] = 4 * i;//期望邊數(shù)for (int e = 0; e < i; e++) {int a = row_match(x, y+e);//上邊int b = row_match(x + i, y+e);//下邊int c = col_match(x+e, y);//左邊int d = col_match(x+e, y +i);//右邊cursize[allsquare] += existedge[a] + existedge[b] + existedge[c] + existedge[d];//實際邊數(shù)contain[allsquare][a] = 1;contain[allsquare][b] = 1;contain[allsquare][c] = 1;contain[allsquare][d] = 1;}++allsquare;}}} } int findsquare() {//找到未被破壞的正方形for (int i = 0; i < allsquare; i++) {if (cursize[i] == fullsize[i]) {return i;}}return -1; } void dfs(int cur) {if (cur >= curbest)return;//比當(dāng)前最優(yōu)值大，剪枝int k = findsquare();if (k == -1) {//沒有完整正方體curbest = cur;return;}for (int i = 0; i < 2 * n*(n + 1); i++) {if (contain[k][i]) {for (int j = 0; j < allsquare; j++) {if (contain[j][i]) {//找與它相鄰邊的正方形cursize[j]--;//包含本身} //這里回溯之所以不考慮contain[j][i]，不置0，是因為它少一條邊之后就是破壞正方形，下次搜索不到}dfs(cur + 1);for (int j = 0; j < allsquare; j++) {if (contain[j][i]) {cursize[j]++;//包含本身}}}}} int main() {int kase = 0;cin >> kase;while (kase-- > 0) {init();curbest = n * n;dfs(0);cout << curbest << endl;}//system("pause");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的UVA1603Square Destroyer破坏正方形的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。