50pts自认思路没问题代码求助
查看原帖
50pts自认思路没问题代码求助
308800
Polynswin楼主2023/10/16 21:57
#include<bits/stdc++.h>
#define rint register int
#define mmt(a,b) memset(a,b,sizeof(a))
#define test(x) cout<<#x<<" = "<<x<<endl
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
#define endl '\n'
#define enter putchar(endl)
//#define int long long
using namespace std;
inline void read(int &x);
inline void ffout(int x);
inline void ffout(string b);
inline void ffout(int x,char b);
inline void ffout(int x,string b);
inline void print(string name,int a[],int r);
const int inf=0x3f3f3f3f,N=1e2+10,M=1e4;
int n,sx,sy,vx,vy,h,t,cnt,m;
int a[N][N],b[N][N];
char sd;
const int p[5]={-114,-1,0,1,0},
		  qx[5]={-514,0,-1,0,1};
struct node{
	int x,y,dir,step;// 1->up 2->left 3->down 4->right
}q[M];
signed main()
{
	rint i,j;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j])b[i][j]=b[i][j-1]=b[i-1][j-1]=b[i-1][j]=1;
		}
//	for(i=1;i<=n;i++)
//	{
//		for(j=1;j<=m;j++)
//		{
//			ffout(b[i][j],' ');
//		}
//		enter;
//	}
	cin>>sy>>sx>>vy>>vx>>sd;
	if(sx==vx&&sy==vy)
	{
		cout<<0;
		return 0;
	}
//	test(sx);test(sy);
//	test(vx);test(vy);
//	cout<<endl<<sd<<endl;
	h=1;t=0;
	if(sd=='S')sd=3;
	if(sd=='W')sd=2;
	if(sd=='E')sd=4;
	if(sd=='N')sd=1;
	q[++t]=node({sx,sy,sd,0});
	b[sx][sy]=1;
	while(h<=t)
	{
		int x=q[h].x,y=q[h].y,d=q[h].dir,curs=q[h].step;
		h++;
		for(rint i=1;i<=4;i++)
			for(rint k=1;k<=3;k++)
			{
				int tx=x+p[i]*k,ty=y+qx[i]*k;
				if(tx<1||ty<1||tx>n||ty>m)break;
				if(b[tx][ty])break;
				b[tx][ty]=1;
				q[++t]=node({tx,ty,i,curs+min(abs(d-i),4-abs(d-i))+1});
				if(tx==vx&&ty==vy)
				{
					ffout(q[t].step);
					return 0;
				}
			}
	}
	cout<<-1;
	return 0;
}









inline void ffout(string b)
{
	int len=b.size();
    for(rint i=0;i<len;++i)putchar(b[i]);
}
inline void read(int &x)
{
	int f=1;x=0;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	x=x*f;
}
inline void ffout(int x)
{
    if(x<0){x=-x; putchar('-'); }
    short sta[63],top=0;
    do{ sta[top++]=x%10; x/=10; }while(x);
    while(top) putchar(sta[--top]+'0');
}
inline void ffout(int x,char b)
{
    if(x<0){x=-x; putchar('-'); }
    short sta[63],top=0;
    do{ sta[top++]=x%10; x/=10; }while(x);
    while(top) putchar(sta[--top]+'0');
    putchar(b);
}
inline void ffout(int x,string b)
{
    if(x<0){x=-x; putchar('-'); }
    short sta[63],top=0;
    do{ sta[top++]=x%10; x/=10; }while(x);
    while(top) putchar(sta[--top]+'0');
    ffout(b);
}
inline void print(string name,int a[],int r)
{
	ffout(name);
	putchar(':');
	for(rint i=1;i<=r;i++)
		ffout(a[i],' ');
	putchar(endl);
}
2023/10/16 21:57
加载中...