โปรแกรม C++ ตรวจสอบภาพสองภาพตรงกันหลังหมุนและเลื่อน

มีภาพสี่เหลี่ยม n×n สองภาพ (first, second) พิกเซลเป็น x (ดำ) หรือ . (ขาว) ตรวจสอบว่า second ตรงกับ first หลังจากหมุน 90° และเลื่อน (translation) ได้กี่ครั้งก็ตาม หากตรงกันคืน true มิฉะนั้น false

ตัวอย่าง: n=4, first={"..x.", "x.x.", "x.xx", "xx.."}, second={"..xx", "x.xx", ".x.x", "..x."} ผลลัพธ์: False (0)

ขั้นตอนการแก้ปัญหา

1. เก็บพิกัดพิกเซล x ของทั้งสองภาพในอาร์เรย์คู่ a, b
2. ถ้าจำนวน x ไม่เท่ากัน → false; ถ้า 0 → true
3. เรียง a แล้วลองหมุน b 4 รอบ (0°, 90°, 180°, 270°):
   • เรียง b ทุกรอบ
   • ฟังก์ชัน find(a,b) ตรวจสอบว่าเวกเตอร์ความต่างระหว่างจุดตรงกันทุกคู่หรือไม่
   • หมุน b โดย (x,y) → (y, n-x-1)
4. ถ้ารอบไหนผ่าน → true

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

bool find(vector<pair<int,int>> x, vector<pair<int,int>> y) {
    int d1 = y[0].first - x[0].first;
    int d2 = y[1].second - x[1].second;
    for (int i = 1; i < x.size(); i++)
        if (y[i].first - x[i].first != d1 || y[i].second - x[i].second != d2)
            return false;
    return true;
}

void rotate(int n, vector<pair<int,int>> &a, vector<pair<int,int>> &b) {
    for (int i = 0; i < b.size(); i++)
        b[i] = {b[i].second, n - b[i].first - 1};
}

bool solve(int n, vector<string> first, vector<string> second) {
    vector<pair<int,int>> a, b;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (first[i][j] == 'x') a.push_back({i,j});
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (second[i][j] == 'x') b.push_back({i,j});
    if (a.size() != b.size()) return false;
    if (a.size() == 0) return true;
    bool check = false;
    sort(a.begin(), a.end());
    for (int i = 0; i < 4; i++) {
        sort(b.begin(), b.end());
        if (find(a, b)) check = true;
        rotate(n, a, b);
    }
    return check;
}

int main() {
    int n = 4;
    vector<string> first = {"..x.", "x.x.", "x.xx", "xx.."};
    vector<string> second = {"..xx", "x.xx", ".x.x", "..x."};
    cout << solve(n, first, second);
    return 0;
}

อินพุต / เอาต์พุต

Input: 4, {"..x.", "x.x.", "x.xx", "xx.."}, {"..xx", "x.xx", ".x.x", "..x."}

Output: 0