社区讨论
90分第八个点wa了,下了测试点,找不到bug,求大佬找错
P1126[CERC1996] 机器人搬重物参与者 13已保存回复 15
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @mi6yrhmr
- 此快照首次捕获于
- 2025/11/20 13:01 4 个月前
- 此快照最后确认于
- 2025/11/20 15:36 4 个月前
CPP
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,x1,y1,x2,y2;
bool vis[55][55][4];
int dre[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int Map1[55][55];
bool Map2[55][55];
struct name
{
int x,y;
int t;
int dir;
};
void bfs()
{
queue <struct name> q;
struct name now;
now.x=x1,now.y=y1;
now.t=0;
char a;
cin>>a;
if(a=='N') now.dir=0;
if(a=='E') now.dir=1;
if(a=='S') now.dir=2;
if(a=='W') now.dir=3;
q.push(now);
while(!q.empty())
{
now=q.front();
q.pop();
//cout<<now.x<<" "<<now.y<<" "<<now.t<<endl;
if(now.x==x2&&now.y==y2)
{
cout<<now.t<<endl;
return;
}
struct name next1;
next1=now;
next1.dir=(now.dir+1)%4;//改变方向
next1.t=now.t+1;
if(!vis[now.x][now.y][next1.dir])
{
vis[now.x][now.y][next1.dir]=true;
q.push(next1);
}
struct name next2;
next2=now;
next2.dir=(now.dir+4-1)%4;//改变方向
next2.t=now.t+1;
if(!vis[now.x][now.y][next2.dir])
{
vis[now.x][now.y][next2.dir]=true;
q.push(next2);
}
struct name next;
for(int i=1;i<=3;i++)
{
int xx=now.x,yy=now.y;
int tmp=i;
bool flag=false;
next=now;
while(tmp>0)
{
xx+=dre[now.dir][0];
yy+=dre[now.dir][1];
if(Map2[xx][yy]==true||xx>n||xx<1||yy>m||yy<1)
{
flag=true;
break;
}
tmp--;
}
if(flag==true) continue;
else
{
if(vis[xx][yy][now.dir]) continue;
next.x=xx,next.y=yy;
next.t=now.t+1;
next.dir=now.dir;
vis[xx][yy][now.dir]=true;
q.push(next);
}
}
}
cout<<"-1"<<endl;
return ;
}
int main ()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>Map1[i][j];
if(Map1[i][j]==1)
{
Map2[i][j]=true;
Map2[i-1][j]=true;
Map2[i][j-1]=true;
Map2[i-1][j-1]=true;
}
}
}
cin>>x1>>y1>>x2>>y2;
bfs();
return 0;
}
测试点是:
20 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
19 4 15 17 E
输出:33
回复
共 15 条回复,欢迎继续交流。
正在加载回复...