회전 및 변환 후 두 이미지가 일치하는지 확인하는 C++ 프로그램

첫 번째와 두 번째로 두 개의 n * n 픽셀 정사각형 이미지가 있다고 가정합니다. 픽셀은 검은색 또는 흰색일 수 있습니다. 이미지는 픽셀이 검은색이면 'x'로 표시되고 흰색이면 '.'로 표시되는 매트릭스 표현으로 제공됩니다. 90° 회전 및 번역 후 두 번째 이미지가 첫 번째 이미지와 일치하는지 확인해야 합니다. 그렇다면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

따라서 입력이 n =4와 같으면 첫 번째 ={"..x.", "x.x.", "x.xx", "xx.."}, 두 번째 ={"..xx", "x. xx", ".x.x", "..x."}이면 출력은 False가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따르겠습니다-

Define a function find(), this will take an array of pairs x, an array of pairs y,
   d1 := first value of y[0] - first value of x[0]
   d2 := second value of y[1] - second value of x[1]
   for initialize i := 1, when i < size of x, update (increase i by 1), do:
      if first value of y[i] - first value of x[i] is not equal to d1 or second value of y[i] - second value of x[i] is not equal to d2, then:
         return false
   return true
Define a function rotate(), this will take n, an array of pairs a, an array of pairs b,
   for initialize i := 0, when i < size of b, update (increase i by 1), do:
      b[i] := make_pair(second value of b[i], n - first value of b[i] - 1)
Define two arrays a, b that can contain integer pairs
for initialize i := 0, when i < n, update (increase i by 1), do:
   s := first[i]
   for initialize j := 0, when j < n, update (increase j by 1), do:
      if s[j] is same as 'x', then:
         insert pair(i, j) at the end of a
for initialize i := 0, when i < n, update (increase i by 1), do:
   s := second[i]
   for initialize j := 0, when j < n, update (increase j by 1), do:
      if s[j] is same as 'x', then:
         insert pair(i, j) at the end of b
if size of a is not equal to size of b, then:
   return false
if size of a is same as 0, then:
   return true
check := false
sort the array a
for initialize i := 0, when i < 4, update (increase i by 1), do:
   sort the array b
   if find(a, b), then:
      check := true
   rotate(n, a, b)
if check is true, then:
   return true
Otherwise
   return false

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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] = make_pair(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++){
      string s = first[i];
      for(int j = 0; j < n; j++){
         if(s[j] == 'x'){ 
            a.push_back(make_pair(i, j));
         }
      }
   }
   for(int i = 0; i < n; i++){
      string s = second[i];
      for(int j = 0; j < n; j++){
          if(s[j] == 'x'){ b.push_back(make_pair(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);
}
if(check){
   return true;
}else{
   return false;
  }
}
int main() { 
   int n = 4; vector<string> first = {"..x.", "x.x.", "x.xx", "xx.."}, second = {"..xx", "x.xx", ".x.x", "..x."};
   cout<< solve(n, first, second);
   return 0;
}

입력

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

출력

0