找茬:从大图中找出特定方块小图,旋转翻转皆可。
4.7华丽地处理字符串
字符串匹配
利用循环哈希法计算大图中所有与小图大小一致的子阵的哈希值。
小图旋转有4种变换,乘以翻转等于8种。先预处理出小图的哈希值,然后与大图的子阵一一比较即可。与其变换大图,明显是变换小图更加高效。
#include <iostream> #include <cstring> using namespace std; #define B 9973 int base64(char ch) { if ('A' <= ch && ch <= 'Z') return ch - 'A'; if ('a' <= ch && ch <= 'z') return ch - 'a' + 26; if ('0' <= ch && ch <= '9') return ch - '0' + 52; return ch == '+' ? 62 : 63; } int w, h, p, image_bit[1024][1024], pattern_bit[128][128], backup[128][128]; char image[1000][200], pattern[100][20]; typedef unsigned long long ull; ull row_hash[1024][1024], hashes[8]; // 计算所有P*P子阵的哈希值所用的临时矩阵与目标的8种变换对应的哈希值 template<size_t raw_rows, size_t raw_cols, size_t bit_rows, size_t bit_cols> inline void base64_to_bit(char (&raw)[raw_rows][raw_cols], int (&bit)[bit_rows][bit_cols], int h) { memset(bit, 0, sizeof(bit)); for (int i = 0; i < h; ++i) for (int j = 0; raw[i][j]; j++) { const int x = base64(raw[i][j]); for (int k = 0; k < 6; ++k) if (x & (1 << k)) bit[i][j * 6 + 5 - k] = 1; } } int main() { while (~scanf("%d%d%d", &w, &h, &p), w) { for (int i = 0; i < h; ++i) scanf(" %s", image[i]); for (int i = 0; i < p; ++i) scanf(" %s", pattern[i]); base64_to_bit(image, image_bit, h); base64_to_bit(pattern, pattern_bit, p); for (int d = 0; d < 8; ++d) // 预处理出小图8种变换的哈希值 { memcpy(backup, pattern_bit, sizeof(pattern_bit)); for (int i = 0; i < p; ++i) for (int j = 0; j < p; ++j) pattern_bit[p - 1 - j][i] = backup[i][j]; // 旋转 if (d == 4) { memcpy(backup, pattern_bit, sizeof(pattern_bit)); for (int i = 0; i < p; ++i) for (int j = 0; j < p; ++j) pattern_bit[i][p - 1 - j] = backup[i][j]; // 翻转 } hashes[d] = 0; for (int i = 0; i < p; ++i) for (int j = 0; j < p; ++j) hashes[d] = hashes[d] * B + pattern_bit[i][j]; } ull t1 = 1ULL; // B的p次方 for (int i = 0; i < p; ++i) t1 *= B; for (int i = 0; i < h; ++i) // 按行方向计算哈希值 { ull e = 0; for (int j = 0; j < w; ++j) { e = e * B + image_bit[i][j]; if (j >= p) e -= t1 * image_bit[i][j - p]; row_hash[i][j] = e; } } ull t2 = 1ULL; for (int i = 0; i < p; ++i) t2 *= t1; int ans = 0; for (int i = p - 1; i < w; i++) // 按列方向计算哈希值 { ull e = 0; for (int j = 0; j < h; ++j) { e = e * t1 + row_hash[j][i]; if (j >= p) e -= t2 * row_hash[j - p][i]; if (j >= p - 1) // pattern是正方形,坐标最小p-1 for (int d = 0; d < 8; ++d) // 8种模式 if (hashes[d] == e) { ans++; break; } } } printf("%d\n", ans); } }
知识共享署名-非商业性使用-相同方式共享:码农场 » AOJ 1312 Where’s Wally 题解《挑战程序设计竞赛》