We have two figures S and T on a two-dimensional grid with square cells. S lies within a grid with N rows and N columns, and consists of the cells where S i,j is #. T lies within the same grid with N rows and N columns, and consists of the cells where T i,j is #. Determine whether it is possible to exactly match S and T by 90-degree rotations and translations.c++代码
时间: 2023-07-02 21:15:46 浏览: 67
以下是实现上述问题的 C++ 代码:
```c++
#include<bits/stdc++.h>
using namespace std;
const int maxn=60;
char s[maxn][maxn],t[maxn][maxn];
int n;
bool check(int x,int y)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(s[i][j]!=t[i+x][j+y])
return false;
return true;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>s[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>t[i][j];
for(int k=0;k<4;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(check(i,j))
{
cout<<"Yes"<<endl;
return 0;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
t[i][j+n]=t[i][j];
t[i+n][j]=t[i][j];
t[i+n][j+n]=t[i][j];
}
}
}
cout<<"No"<<endl;
return 0;
}
```
首先,我们需要两个二维字符数组 `s` 和 `t` 分别存储两个图形。然后,我们需要一个函数 `check` 判断是否可以通过旋转和平移将两个图形完全匹配。
具体来说,我们枚举旋转的次数,然后枚举平移的距离,检查是否可以将 `t` 平移和旋转后与 `s` 完全匹配。匹配的方法是枚举 `t` 的左上角坐标 `(i,j)`,然后检查 `t` 中从 `(i,j)` 开始的大小与 `s` 相同的矩形是否与 `s` 完全匹配。
需要注意的是,为了方便处理旋转和平移,我们可以将 `t` 沿着横、竖、斜方向复制一遍,使得 `t` 中的任意一个位置都可以通过平移和旋转得到与之匹配的 `s`。
最后,如果找到了一组旋转和平移能够使得 `s` 和 `t` 完全匹配,则输出 "Yes",否则输出 "No"。