94分WA12,36,39,急!!!
查看原帖
94分WA12,36,39,急!!!
658303
ouliang楼主2024/4/14 11:26
#include<bits/stdc++.h>
using namespace std;
int n,m,bx,by,dx[5]={1,1,-1,-1},dy[5]={1,-1,-1,1},s[600][600],ix[5]={0,0,-1,-1},iy[5]={0,-1,-1,0};
bool a[600][600],pd[5]={0,1,0,1};
struct wz{
	int x,y,z;
}cr,cc;
deque<wz> q;
void bfs()
{
	int x,y,gx,gy;
	bool p;
	cr.x=cr.y=cr.z=0;
	q.push_front(cr);
	while(!q.empty())
	{
		cc=q.front();q.pop_front();
		for(int i=0;i<4;i++)
		{
			gx=cc.x+ix[i];
			gy=cc.y+iy[i];
			x=cc.x+dx[i];
			y=cc.y+dy[i];
			if(a[gx][gy]!=pd[i])
			  p=1;
			else
			  p=0;
			if(x>n+1 || x<1 || y>m+1 || y<1 || s[x][y]<=p+cc.z)
			  continue;
			if(p)
			{
				cr.x=x;
				cr.y=y;
				cr.z=cc.z+1;
				s[x][y]=cr.z;
				q.push_back(cr);
			}
			else
			{
				cr=cc;
				cr.x=x;
				cr.y=y;
				s[x][y]=cr.z;
				q.push_front(cr);
			}
		}
	}
	cout<<s[n+1][m+1];
}
int main()
{
	char c;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	  {
		cin>>c;
		a[i][j]= c=='/';
	    s[i][j]=50000000;
	  }
	if((n+m)%2)
	{
		cout<<"NO SOLUTION";
		return 0;
	}
	s[n+1][m+1]=s[n+1][m]=s[n][m+1]=50000000;
	bfs();
	return 0;
}
2024/4/14 11:26
加载中...