AOJ 1312 Where’s Wally 题解《挑战程序设计竞赛》

AOJ 1312 Where's Wally 

找茬：从大图中找出特定方块小图，旋转翻转皆可。

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 题解《挑战程序设计竞赛》