社区讨论
蒟蒻求助!!不知道哪里有问题!帮忙看下吧
P1205[USACO1.2] 方块转换 Transformations参与者 2已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @lze9a2mc
- 此快照首次捕获于
- 2024/08/03 22:55 2 年前
- 此快照最后确认于
- 2024/08/04 09:25 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
int n;
char mp[20][20];
char ans[20][20];
bool vis1[20][20];
bool vis2[20][20];
int ty[4] = {1,0,-1, 0};
int tx[4] = {0,1,0,-1};
queue <int> qx;
queue <int> qy;
queue <int> mx;
queue <int> my;
int bfs(int x,int y)
{
mx.push(0);
my.push(0);
qx.push(x);
qy.push(y);
while(!qx.empty() && !qy.empty() && !mx.empty() && !my.empty())
{
if(mp[qx.front()][qy.front()] != ans[mx.front()][my.front()])
{
while(!qx.empty() && !qy.empty())
{
qx.pop();
qy.pop();
}
while(!mx.empty() && !my.empty())
{
mx.pop();
my.pop();
}
return 0;
}
for(int i = 0; i<4; i++)
{
int dx = qx.front()+tx[i];
int dy = qy.front()+ty[i];
int nx = mx.front()+tx[i];
int ny = my.front()+ty[i];
if(dx >= 0 && dy >= 0 && dx < n && dy < n && vis1[dx][dy] == 0)
{
qx.push(dx);
qy.push(dy);
vis1[dx][dy] = 1;
}
if(nx >= 0 && ny >= 0 && nx < n && ny < n && vis2[nx][ny] == 0)
{
mx.push(nx);
my.push(ny);
vis2[nx][ny] = 1;
}
}
qx.pop();
qy.pop();
mx.pop();
my.pop();
}
return 1;
}
int fanzhuan()
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j<n/2; j++)
{
swap(mp[i][j],mp[i][n-1-j]);
}
}
return 0;
}
int main()
{
int n;
cin >> n;
for(int i = 0; i<n; i++)
{
for(int j = 0; j<n; j++)
{
cin >> mp[i][j];
}
}
if(bfs(0,n-1))
{
cout << 1;
return 0;
}
memset(vis1,0,sizeof vis1);
memset(vis2,0,sizeof vis2);
if(bfs(n-1,n-1))
{
cout << 2;
return 0;
}
memset(vis1,0,sizeof vis1);
memset(vis2,0,sizeof vis2);
if(bfs(n-1,0))
{
cout << 3;
return 0;
}
memset(vis1,0,sizeof vis1);
memset(vis2,0,sizeof vis2);
fanzhuan();
if(bfs(0,0))
{
cout << 4;
}
memset(vis1,0,sizeof vis1);
memset(vis2,0,sizeof vis2);
if(bfs(0,n-1) || bfs(n-1,n-1) || bfs(n-1,0))
{
cout << 5;
return 0;
}
memset(vis1,0,sizeof vis1);
memset(vis2,0,sizeof vis2);
fanzhuan();
if(bfs(0,0))
{
cout << 6;
return 0;
}
cout << 7;
return 0;
}
代码有点长,个人看还是很好理解的,麻烦大犇帮忙看下,谢谢!!!
回复
共 5 条回复,欢迎继续交流。
正在加载回复...