UVA - 11846 Finding Seats Again (DFS搜索对象)

题意：有一个n*n（n<20）的座位矩阵里坐着k（k26）个研究小组。每个小组的座位都是矩形形状。输入每个小组组长的位置和该组的成员个数，找到一种可能的座位方案。

分析：方法肯定是用dfs，但根据搜索对象不同，可以简化搜索，我是以数字为对象进行搜索，结果却是超时。想想就纳闷，10秒竟然超了，虽然我没有剪枝。

参考网上大佬方法，以空地作为枚举对象，每次寻找枚举行和列，当矩形里恰好有一个数字，且数字等于矩形大小，就符号条件，当矩形大小超过9就剪枝。

失败方法：

#include
#include
#include
#include
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
#include
#include
#include
#include
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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！