社区讨论

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 条回复,欢迎继续交流。

正在加载回复...