本文主要是介绍uva519 - Puzzle (II)（回溯），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：uva519 - Puzzle (II)
题目大意：给出拼图，要求将给出的拼图拼成 n行m列的矩形，可以输出yes，不行输出no。
解题思路：直接dfs，但是需要剪枝。
1、判断 F 的出现个数是否等于 2 * ( n + m) , 还有IO的个数是否匹配，不匹配就直接剔除，。
2、边界问题要处理，例如第一行第N行，第一列第M列，这些地方的拼图是有要求的，这些边界拼图的的外围都要是F。例如第一行的top要是F，不是F的直接不考虑。（这点导致我TL了N次）
3、相同形状的拼图，在相同一层的dfs里可以不用在考虑了。因为前面出现了一样的但是结果是不行的，所以和他相同的就不需要考虑了，但是这个仅限于同一层dfs里面，因为如果不是同一层，那么可能前面与他相邻的拼图变化了，这样这个形状的拼图可能在这种情况下就是可以的。相同形状的可以用三进制数表示，也可以排序后，直接字符串比较。
4、可以将这些拼图事先分好组，上面为F一组，下面为F的为1组，我这里分了12组。这样查找的时候就可以把范围缩小了。
前三点做到了就可以过了。
代码：（做到四点）
#include <stdio.h>
#include <string.h>const int N = 50;
const int M = 10;struct PUZZLE {int top;int left;int bottom;int right;
} puzzle[N];int rec[M][M], vis[N], list[M + 2][N];
char str[M];
int n, m, cnt[M + 2], p_value[N];
bool flag;int hash (int k) {int num;num = puzzle[k].top + puzzle[k].left * 3 + puzzle[k].bottom * 9 + puzzle[k].right * 27; return num;
}int interpret (char ch) {if (ch == 'F')return 0;if (ch == 'O')return 1;if (ch == 'I')return 2;
}void clasify (int i, int k) {if (str[i] == 'F')list[i * 3][cnt[i * 3]++] = k;else if (str[i] == 'I')list[i * 3 + 1][cnt[i * 3 + 1]++] = k;elselist[i * 3 + 2][cnt[i * 3 + 2]++] = k;
}void handle (int k) {for (int i = 0; i < strlen (str); i++) {if (i == 0) puzzle[k].top = interpret(str[i]);else if (i == 1) puzzle[k].right = interpret(str[i]); else if (i == 2) puzzle[k].bottom = interpret(str[i]); elsepuzzle[k].left = interpret(str[i]);clasify (i, k); }
}void dfs (int x, int y) {if (flag)return;if (x > n) {flag = 1;return ;}int k, map[M * M];memset (map , 0, sizeof (map));if (x == 1)k = 0;else if (x == n)k = 6;else if (y == 1)k = 9;else if (y == m)k = 3;else {if (puzzle[rec[x - 1][y]].bottom == 0) k = 0; else if (puzzle[rec[x - 1][y]].bottom == 1)k = 1;else if (puzzle[rec[x - 1][y]].bottom == 2)k = 2;else if (puzzle[rec[x][y - 1]].right == 0)k = 9;else if (puzzle[rec[x][y - 1]].right == 1)k = 10;else if (puzzle[rec[x][y - 1]].right == 2)k = 11;}for (int i = 0; i < cnt[k]; i++) {if (map[p_value[list[k][i]]])continue;if (vis[list[k][i]])continue;if (!((puzzle[list[k][i]].left + puzzle[rec[x][y - 1]].right) % 3) && !((puzzle[list[k][i]].top + puzzle[rec[x - 1][y]].bottom) % 3)) {rec[x][y] = list[k][i];vis[list[k][i]] = 1;if (y + 1 > m) dfs (x + 1, 1);elsedfs (x, y + 1);if (flag)return;vis[list[k][i]] = 0;map[p_value[list[k][i]]] = 1;}}
}void init () {flag = 0;memset (cnt, 0, sizeof (cnt));memset (rec, 0, sizeof (rec));memset (vis, 0, sizeof (vis));memset (list, 0, sizeof (list));puzzle[0].top = puzzle[0].left = puzzle[0].bottom = puzzle[0].right = 0;}int main () {while (scanf ("%d%d", &n, &m) , n || m) {init (); for (int i = 1 ; i <= n * m; i++) {scanf ("%s", str);handle(i);}int n1 = 0, n2 = 0;for (int i = 0; i < 4; i++) {n1 += cnt[i * 3 + 1];n2 += cnt[i * 3 + 2];}if (cnt[0] == m && n1 == n2 && cnt[3] == n && cnt[6] == m && cnt[9] == n) { for (int i = 1; i <= n * m; i++) p_value[i] = hash(i);dfs (1, 1);}printf ("%s\n", flag == 1?"YES":"NO");}return 0;
}#include <stdio.h>
#include <string.h>const int N = 50;
const int M = 10;struct PUZZLE {int top;int left;int bottom;int right;
} puzzle[N];int rec[M][M], vis[N];
char str[M];
int n, m, p_value[N];
bool flag;
int c1, c2, c0;int hash (int k) {int num;num = puzzle[k].top + puzzle[k].left * 3 + puzzle[k].bottom * 9 + puzzle[k].right * 27; return num;
}int interpret (char ch) {if (ch == 'F')return 0;if (ch == 'O')return 1;if (ch == 'I')return 2;
}void handle (int k) {for (int i = 0; i < strlen(str); i++) {if (i == 0) puzzle[k].top = interpret(str[i]);else if (i == 1) puzzle[k].right = interpret(str[i]); else if (i == 2) puzzle[k].bottom = interpret(str[i]); elsepuzzle[k].left = interpret(str[i]);if (str[i] == 'F')c0++;else if (str[i] == 'O')c2++;elsec1++;}
}void dfs (int x, int y) {if (flag)return;if (x > n) {flag = 1;return ;}int k, map[M * M];memset (map , 0, sizeof (map));for (int i = 1; i <= n * m; i++) {if (x == 1 && puzzle[i].top != 0)continue;if (x == n && puzzle[i].bottom != 0)continue;if (y == 1 && puzzle[i].left != 0)continue;if (y == m && puzzle[i].right != 0)continue;if (map[p_value[i]])continue;if (vis[i])continue;if (!((puzzle[i].left + puzzle[rec[x][y - 1]].right) % 3) && !((puzzle[i].top + puzzle[rec[x - 1][y]].bottom) % 3)) {rec[x][y] = i;vis[i] = 1;if (y + 1 > m) dfs (x + 1, 1);elsedfs (x, y + 1);if (flag)return;vis[i] = 0;map[p_value[i]] = 1;}}
}void init () {flag = 0;memset (rec, 0, sizeof (rec));memset (vis, 0, sizeof (vis));c1 = c2 = c0 = 0;puzzle[0].top = puzzle[0].left = puzzle[0].bottom = puzzle[0].right = 0;}int main () {while (scanf ("%d%d", &n, &m) , n || m) {init (); for (int i = 1 ; i <= n * m; i++) {scanf ("%s", str);handle(i);}if (c1 == c2 && c0 == 2 * (m + n)) { for (int i = 1; i <= n * m; i++) p_value[i] = hash(i);dfs (1, 1);}printf ("%s\n", flag == 1?"YES":"NO");}return 0;
}这篇关于uva519 - Puzzle (II)（回溯）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
