《关于调了三个半小时没调出来这个题这件事》
查看原帖
《关于调了三个半小时没调出来这个题这件事》
231543
bloodstalk楼主2022/4/17 11:31

这个题本来自己写不对,参考了题解有了思路,然后还是不对,请朋友们耗费一些时间帮我看一下吧(有注释,不多)

#include<bits/stdc++.h>
using namespace std;

int gezi[55][55];
int vis[55][55][5];

int n,m;
int startx,starty,endx,endy;
char direct;bool flag;

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

struct node
{
	int x;
	int y;
	int step;
	int direct;/*E是0,S是1,W是2,N是3*/
}now,endd,andd;

queue <node> q;

void bfs(int x,int y,int dt)
{
	now.x=x;
	now.y=y;
	now.step=0;
	now.direct=dt;
	q.push(now);
	while(!q.empty())
	{
		now=q.front();
		q.pop();
		if(now.x==endx && now.y==endy) {cout<<now.step;exit(0);}
		for(int i=1;i<=3;i++)
		{
			endd.x=now.x+dx[now.direct]*i;
			endd.y=now.y+dy[now.direct]*i;/*朝着一个方向走,不转向的情况*/
			if(endd.x<1 || endd.x>=n || endd.y<1 || endd.y>=m || gezi[endd.x][endd.y]) break; /*如果这个不能走,那么往后都不能走*/
            else if(!vis[endd.x][endd.y][now.direct])
			{
				vis[endd.x][endd.y][now.direct]=1;
				endd.step=now.step+1;
				endd.direct=now.direct;
				q.push(endd);	
			}
		}
		andd=now;/*转向的两个情况*/
		andd.direct=now.direct-1;if(andd.direct==-1) andd.direct=3;
		if(!vis[andd.x][andd.y][andd.direct]){vis[andd.x][andd.y][andd.direct]=1;andd.step=now.step+1;q.push(andd);}
		andd.direct=now.direct+1;if(andd.direct==4) andd.direct=0;
		if(!vis[andd.x][andd.y][andd.direct]){vis[andd.x][andd.y][andd.direct]=1;andd.step=now.step+1;q.push(andd);}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
		{
            scanf("%d",&gezi[i][j]);
            if(gezi[i][j])
			{
                gezi[i-1][j-1]=1;
                gezi[i-1][j]=1;
                gezi[i][j-1]=1;/*走不了,那么就说明这四个点都走不了*/
            }
        }
	scanf("%d%d%d%d%c",&startx,&starty,&endx,&endy,&direct);
	int dire=0;
	if(direct=='E') dire=0;
	else if(direct=='S') dire=1;
	else if(direct=='W') dire=2;
	else dire=3; /*四个方向*/
	vis[startx][starty][dire]=1;
	if(startx>=n || startx<1 || starty>=m || starty<1 || gezi[startx][starty]){cout<<"-1";return 0;}/*初始点特判*/
	bfs(startx,starty,dire);
	cout<<"-1";/*无解的情况*/
	return 0;	
} 
2022/4/17 11:31
加载中...