首页 > 代码库 > UVa 1602 网格动物（回溯）
UVa 1602 网格动物（回溯）
https://vjudge.net/problem/UVA-1602
题意：计算n连通块不同形态的个数。
思路：
实在是不知道该怎么做好，感觉判重实在是太麻烦了。
判重就是判断所有格子位置是否都相同，这样我们可以定义一个结构体来保存每个格子的坐标点，用set容器poly来保存这些格子，然后再用一个set容器poly_set来保存指定数量i个连通块的各个图形的坐标点,也就是说该容器是用来保存poly的。(不太好解释，具体可以看代码。)因为图形必须是连通的，所以在添加第i个格子的时候必定是在i-1个格子的基础上添加的。这样我们在添加第i个格子的时候，只需要遍历保存第(i-1)个连通块的poly_set，然后遍历它当中的每个格子，每个格子可以往4个方向发展。然后进行判断。
因为一个连通块可以在不同的坐标点，即使他们形状相同，也许坐标是不同的。所以首先需要将它们标准化，也就是平移。平移就是选取连通块中最小的x和y值，并将（x，y）定为（0,0）原点，这样每个图形就可以比较坐标了。当然，判重时还需要进行旋转，180度翻转操作，旋转的话就是每个格子都顺时针旋转90度即可。相应的几何变换为(x,y)->(y,-x)。180度翻转得几何变化就是(x,y)->(x,-y)。旋转和翻转后需要重新平移来标准化。
由于这道题数据不大，可以直接打表，这样数据多的时候比较快。
这道题目确实很不错，不过真的是挺麻烦的，借鉴了大神们的代码之后，看了很久终于理解了做法。
1 #include<iostream> 2 #include<cstring> 3 #include<set> 4 #include<algorithm> 5 using namespace std; 6 7 const int dx[] = { -1, 1, 0, 0 }; 8 const int dy[] = { 0, 0, -1, 1 }; 9 const int N = 10; 10 int n, w, h; 11 int ans[15][15][15]; //打表之后的答案 12 13 struct Cell //定义单元格 14 { 15 int x, y; 16 Cell(int a, int b) { x = a; y = b; } 17 Cell() {} 18 bool operator < (const Cell&rhs) const //重载小于号，在set容器中排序 19 { 20 return x < rhs.x || (x == rhs.x && y < rhs.y); 21 } 22 }; 23 24 typedef set<Cell>poly; //坐标的集合，也就是一个连通块（1，2，3....） 25 set<poly> poly_set[15]; //有i个Cell的poly集合 26 27 28 29 //规范化到最小点（0,0) 30 poly normalize(poly& p) 31 { 32 poly this_p; 33 int min_x = p.begin()->x, min_y = p.begin()->y; 34 //找到最小的x和y坐标 35 for (poly::iterator q = p.begin(); q != p.end(); q++) 36 { 37 if (q->x < min_x) min_x = q->x; 38 if (q->y < min_y) min_y = q->y; 39 } 40 //平移 41 for (poly::iterator q = p.begin(); q != p.end(); q++) 42 { 43 this_p.insert(Cell(q->x - min_x, q->y - min_y)); 44 } 45 return this_p; 46 } 47 48 //向右翻转90度 49 poly rotate(poly& p) 50 { 51 poly this_p; 52 for (poly::iterator q = p.begin(); q != p.end(); q++) 53 { 54 this_p.insert(Cell(q->y, -q->x)); //x值为原来的y值，y值为原来的-x值 55 } 56 //旋转之后需要将它规范化 57 return normalize(this_p); 58 } 59 60 //向下翻转180度 61 poly flip(poly& p) 62 { 63 poly this_p; 64 for (poly::iterator q = p.begin(); q != p.end(); q++) 65 { 66 this_p.insert(Cell(q->x, -q->y)); //x坐标不变，y变号 67 } 68 return normalize(this_p); 69 } 70 71 void check(const poly& this_p, Cell& this_c) 72 { 73 poly p = this_p; 74 p.insert(this_c); 75 76 //标准化 77 p = normalize(p); 78 int n = p.size(); 79 80 for (int i = 0; i < 4; i++) 81 { 82 //if (poly_set[n].find(p) != 0 ) 83 if (poly_set[n].find(p) != poly_set[n].end()) //已存在 84 return; 85 //对该连通块向右旋转90度 86 p = rotate(p); 87 } 88 //将该连通块翻转180度 89 p = flip(p); 90 for (int i = 0; i < 4; i++) 91 { 92 if (poly_set[n].find(p) != poly_set[n].end()) 93 return; 94 p = rotate(p); 95 } 96 //如果未重复则加入该连通块的集合 97 poly_set[n].insert(p); 98 } 99 100 101 void Generate() //打表102 {103 //先生成一个连通块104 poly s;105 s.insert(Cell(0, 0));106 poly_set[1].insert(s); //插入到一个Cell的poly集合，只有一个格子的连通块只有这么一个107 //根据有i-1个Cell(格子）的poly（连通块）集合来生成有i个Cell的poly集合108 for (int i = 2; i <= N; i++) //从生成第2个格子开始，一直到第10个109 {110 //遍历有i-1个Cell的连通块集合111 for (set<poly>::iterator p = poly_set[i - 1].begin(); p != poly_set[i - 1].end(); p++)112 {113 //在每个连通块中遍历每个Cell即格子114 for (poly::const_iterator q = p->begin(); q != p->end(); q++)115 {116 for (int j = 0; j < 4; j++)117 {118 Cell new_c(q->x + dx[j], q->y + dy[j]); //生成新格子119 if (p->find(new_c) == p->end()) //如果在该坐标上还没有Cell（格子），则继续往下判断120 {121 check(*p, new_c); //判断当前连通块加上这个Cell坐标后是否存在122 }123 }124 }125 }126 }127 128 //生成答案129 for(int i = 1; i <= N;i++)130 {131 for (int w = 1; w <= i; w++)132 {133 for (int h = 1; h <= i; h++)134 {135 int cnt = 0;136 for (set<poly>::iterator p = poly_set[i].begin(); p != poly_set[i].end(); p++)137 {138 int max_x = p->begin()->x, max_y = p->begin()->y;139 for (poly::iterator q = p->begin(); q != p->end(); q++)140 {141 if (max_x < q->x) max_x = q->x;142 if (max_y < q->y) max_y = q->y;143 }144 145 if (min(max_x, max_y) < min(w, h) && max(max_x,max_y) < max(w, h)) //判断能够放入网格的条件146 cnt++;147 148 }149 ans[i][w][h] = cnt;150 }151 }152 }153 }154 155 156 int main()157 {158 //freopen("D:\\txt.txt", "r", stdin);159 Generate(); //打表160 while (cin >> n >> w >> h)161 {162 cout << ans[n][w][h] << endl;163 }164 return 0;165 }
UVa 1602 网格动物（回溯）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。