放牧代码和思想
专注自然语言处理、机器学习算法

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

目录

hankcs.com 2017-02-06 下午8.50.37.png挑战程序设计竞赛第二版.jpg

AOJ 1312 Where's Wally 

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

4.7华丽地处理字符串 

字符串匹配 

利用循环哈希法计算大图中所有与小图大小一致的子阵的哈希值。

hankcs.com 2017-02-06 下午8.50.37.png

小图旋转有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);
    }
}

hankcs.com 2017-02-06 下午8.49.43.png

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » AOJ 1312 Where’s Wally 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机