Untitled

 avatar
unknown
plain_text
a year ago
1.9 kB
5
Indexable
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

#define MAX_N (10001)
#define MAX_M (10)
#define ll long long

int n, m;
ll imgs[MAX_N][3];
unordered_map<ll, vector<int>> hashImg[3];

int cmpImg(ll img1[3], ll img2[3]) {
    int cnt = 0;
    for(int i = 0; i < 3; i++) {
        if(img1[i] == img2[i])  continue;
        int j = 0;
        while(img1[i] >> j != 0 || img2 [i] >> j != 0) {
            if((img1[i] >> j) % 2 != (img2[i] >> j) % 2) cnt++;
            if(cnt > 2) return cnt;
            j++;
        }
    }
    return cnt;
}

void getSeg(char image[MAX_M][MAX_M], ll segs[3]) {
    int segSize = m * m / 3;
    if(m * m % 3 == 2) segSize += 1;
    for(int i = 0; i < 3; i++) {
        segs[i] = 0;
        int end = i * segSize + segSize;
        if(i == 2) end = m*m;
        for(int j = i * segSize; j < end; j++) {
            segs[i] = (segs[i] << 1) + image[j/m][j%m];
        }
    }
}

void init(int N, int M, char mImageList[MAX_N][MAX_M][MAX_M]) {
	n = M;
    m = M;
    hashImg[0].clear();
    hashImg[1].clear();
    hashImg[2].clear();
    for(int i = 0; i < N; i++) {
        getSeg(mImageList[i], imgs[i + 1]);
        for(int j = 0; j < 3; j++) {
            hashImg[j][imgs[i+1][j]].push_back(i + 1);
        }
    }
}
int findImage(char mImage[MAX_M][MAX_M]) {
    ll segs[3];
    getSeg(mImage, segs);
    int diff = 100, id = 10001;
    for(int i = 0; i < 3; i++) {
        if(hashImg[i].find(segs[i]) == hashImg[i].end() ) continue;
        int *ref = &hashImg[i][segs[i]][0];
        int size = hashImg[i][segs[i]].size();
        int cnt = 0;
        for(int j = 0; j < size; j++) {
            cnt = cmpImg(segs, imgs[ref[j]]);
            if(cnt < diff || (cnt == diff && ref[j] < id)) {
                diff = cnt;
                id = ref[j];
            }
        }
    }
	return id;
}
Editor is loading...
Leave a Comment