WA#4,求助
查看原帖
WA#4,求助
1314007
Zhall_Dreamy楼主2024/12/16 20:42
#include<bits/stdc++.h>
//#define int long long
using namespace std;
inline int read()
{
	int val=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		val*=10,val+=ch-'0',ch=getchar();
	return val*f;
}
inline void write(const int& val)
{
	if(val<0)
	{
		putchar('-'),write(-val);
		return;
	}
	if(val>9) write(val/10);
	putchar(val%10+'0');
}
int n,m;
struct nd
{
	int x,y,st;
	nd(int a=0,int b=0,int s=0):x(a),y(b),st(s) { }
}s,e,d;
char ch[2005][2005];
bool mp[2005][2005];
queue<nd> q;
const int fx[4]={1,-1,0,0},fy[4]={0,0,1,-1};
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>ch[i][j],mp[i][j]=(ch[i][j]=='.'||ch[i][j]=='S'||ch[i][j]=='G');
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(ch[i][j]=='^')
			{
				for(int k=1;mp[i-k][j];k++)
					mp[i-k][j]=false;
			}
			else if(ch[i][j]=='v')
			{
				for(int k=1;mp[i+k][j];k++)
					mp[i+k][j]=false;
			}
			else if(ch[i][j]=='<')
			{
				for(int k=1;mp[i][j-k];k++)
					mp[i][j-k]=false;
			}
			else if(ch[i][j]=='>')
			{
				for(int k=1;mp[i][j+k];k++)
					mp[i][j+k]=false;
			}
			else if(ch[i][j]=='S')
			{
				s.x=i,s.y=j;
			}
			else if(ch[i][j]=='G')
			{
				e.x=i,e.y=j;
			}
		}
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++)
//			cout<<mp[i][j];
//		cout<<endl;
//	}
	q.push(s);
	while(!q.empty())
	{
		d=q.front(),q.pop();
		if(d.x==e.x&&d.y==e.y)
		{
			write(d.st),putchar('\n');
			return 0;
		}
		for(int i=0;i<4;i++)
		{
			int xx=d.x+fx[i],yy=d.y+fy[i];
			if(mp[xx][yy])
				q.push(nd(xx,yy,d.st+1)),mp[xx][yy]=false;
		}
	}
	puts("-1");
	return 0;
}

改者必关

2024/12/16 20:42
加载中...