題意：有一個n*n（n<20）的座位矩陣里坐著k（k26）個研究小組。每個小組的座位都是矩形形狀。輸入每個小組組長的位置和該組的成員個數，找到一種可能的座位方案。

分析：方法肯定是用dfs，但根據搜索對象不同，可以簡化搜索，我是以數字為對象進行搜索，結果卻是超時。想想就納悶，10秒竟然超了，雖然我沒有剪枝。

參考網上大佬方法，以空地作為枚舉對象，每次尋找枚舉行和列，當矩形里恰好有一個數字，且數字等于矩形大小，就符號條件，當矩形大小超過9就剪枝。

失敗方法：

#include<iostream> #include<time.h> #include<queue> #include<stdlib.h> using namespace std; int n, k; char mp[20 + 5][20 + 5];bool dfs(int x,int y,char t) {if (x == n && y == n)return true; if (y == n) {x++; y = 0;if (x == n)return true;}int flag = 0;for (int i = y; i < n; i++) {if (mp[x][i] >= '0'&&mp[x][i] <= '9') {flag = 1;int k = mp[x][i] - '0';int flag2 = 0;for (int j = 1; j <= 9; j++) {flag2 = 0;if (k%j)continue;int ok = 1; int ant = 0; int r1=0, r2=0, c1=0, c2=0;int x1 = i + 1 - k / j; int x2 = i - 1 + k / j;int y1 = x + 1 - j; int y2 = x - 1 +j;if (x1 < 0)x1 = 0; if (y1 < 0)y1 = 0;if (x2 >= n)x2 = n - 1; if (y2 >= n)y2 = n - 1;if (x2 - x1 + 1 < k / j || y2 - y1 + 1 < j)continue;for (int z = x1; z <= x2; z++) {for (int c = y1; c <= y2; c++) {ok = 1;ant = 0; r1 = z; r2 = z + k / j; c1 = c; c2 = c + j;for (int l = r1; l < r2; l++) {for (int p = c1; p < c2; p++)if (mp[p][l] != '.' && (p != x || l != i)) {ok = 0;break;}if (!ok)break;} if (!ok)continue;//回溯flag2 = 1;char tmp[20 + 5][20 + 5];for (int o1 = r1; o1 < r2; o1++)for (int o2 = c1; o2 < c2; o2++) {tmp[o2][o1] = mp[o2][o1];mp[o2][o1] = t;}if (dfs(x, r2, t + 1))return true;for (int o1 = r1; o1 < r2; o1++)for (int o2 = c1; o2 < c2; o2++) {mp[o2][o1]= tmp[o2][o1] ;}}if (!ok)continue;}if (!ok)continue;}if (!flag2)return false;}}if (!flag) { x++; y = 0;if (x == n)return true;if (dfs(x, y, t))return true;}return false; } int main() {while (cin >> n >> k&&n&&k) {for (int i = 0; i < n; i++)cin >> mp[i];dfs(0, 0, 'A');for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++)cout << mp[i][j];cout << endl;}}return 0; }

?

大佬的方法：

#include<iostream> #include<time.h> #include<queue> #include<stdlib.h> #include<cstring> using namespace std; int n, k; char mp[20 + 5][20 + 5]; char ans[25][25]; bool dfs(int t,char ac) {while (ans[t / n][t%n] != '.')t++;if (t == n * n)return true;int rw = t / n, cl = t % n, lim = n;for (int r = rw; r < n; r++) {for (int c = cl; c < lim; c++) {if (ans[r][c] != '.') { lim = c; break; }int sum = (r - rw + 1)*(c - cl + 1);if (sum > 9) { lim = c; break; }//rw會越來越大，現在c已經超了，在變大之后肯定還會超int d = 100;int flag = 1;for (int i = rw; i <= r; i++) {for (int j = cl; j <= c; j++) {if (mp[i][j] != '.') {if (d != 100) { flag = 0; break; }d = mp[i][j] - '0';}}if (!flag)break;}if (!flag) { lim = c; break; }if (d < sum) { lim = c; break; }if (d > sum)continue;for (int i = rw; i <= r; i++)for (int j = cl; j <= c; j++)ans[i][j] = ac;if (dfs(t + c - cl + 1, ac + 1))return true;for (int i = rw; i <= r; i++)for (int j = cl; j <= c; j++)ans[i][j] = '.';}}return false; } int main() {while (cin >> n >> k&&n&&k) {memset(ans, '.', sizeof(ans));for (int i = 0; i < n; i++)cin >> mp[i];dfs(0,'A');for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++)cout << ans[i][j];cout << endl;}}return 0; }

?

總結

以上是生活随笔為你收集整理的UVA - 11846 Finding Seats Again (DFS搜索对象)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。