AcWing 5379. 旋转和翻转
原题链接
中等
作者:
NULL_549
,
2023-12-30 21:28:16
,
所有人可见
,
阅读 57
bfs 只用不停旋转90 和 按x轴对称反转即可
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin>>n;
string str1,str2;
for(int j=0;j<n*n;j++){
char c;
cin>>c;
str1+=c;
}
for(int j=0;j<n*n;j++){
char c;
cin>>c;
str2+=c;
}
function<bool(string)> bfs=[&](string start)->bool{
unordered_map<string,int> h;
queue<string> q;
q.push(start);
while(q.size()){
auto t=q.front();
q.pop();
if(h[t]) continue;
h[t]=1;
if(t==str2) return true;
vector<string> str;
for(int i=0;i<n;i++){
string s;
for(int j=i*n;j<n*(i+1);j++){
s+=t[j];
}
str.push_back(s);
}
string s;
for(int i=0;i<n;i++)//反转90
for(int j=n-1;j>=0;j--)
s+=str[j][i];
q.push(s);
s="";
for(int i=n-1;i>=0;i--)//对称
for(int j=0;j<n;j++)
s+=str[i][j];
q.push(s);
}
return false;
};
if(bfs(str1)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return ;
}
int main(){
solve();
return 0;
}
借楼😂AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/187089/