求dalao差错
查看原帖
求dalao差错
199459
Masna_Kimoyo楼主2020/12/27 15:42

样例点过了,64分qwq

#include<bits/stdc++.h>
using namespace std;
deque <int> x,y;
const int N=505;
const int dx[N]={-1,-1,1,1};
const int dy[N]={-1,1,-1,1};
const int ix[N]={-1,-1,0,0};
const int iy[N]={-1,0,-1,0};
char a[4]={'\\','/','/','\\'};
char s[N][N];
int n,m;
int vis[N][N];
inline int read()
{
	int x=0;
	bool w=0;
	char c=getchar();
	while(!isdigit(c))
		w|=c=='-',c=getchar();
	while(isdigit(c))
		x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void bfs()
{
	memset(vis,0x3f,sizeof(vis));
	x.push_front(1);
	y.push_front(1);
	vis[1][1]=0;
	while(!x.empty())
	{
		int xx=x.front();
		int yy=y.front();
		x.pop_front();
		y.pop_front();
		for(register int i=0;i<4;++i)
		{
			int dnx=xx+dx[i];
			int dny=yy+dy[i];
			int dix=xx+ix[i];
			int diy=yy+iy[i];
			if(dnx<1 || dny<1 || dnx>n+1 || dny>m+1)
				continue;
			if(a[i]!=s[dix][diy])
			{
				int t=vis[xx][yy]+1;
				if(t<vis[dnx][dny])
				{
					x.push_back(dnx);
					y.push_back(dny);
					vis[dnx][dny]=t;
				}
			}
			else
			{
				int t=vis[xx][yy];
				if(t<vis[dnx][dny])
				{
					x.push_front(dnx);
					y.push_front(dny);
					vis[dnx][dny]=t;
				}
			}
		}
	}
	cout<<vis[n][m];
}
int main()
{
	n=read(),m=read();
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j)
			cin>>s[i][j];
	if((n+m)&1)
	{
		cout<<"NO SOLUTION";
		return 0;
	}
	bfs();
	return 0;
}
2020/12/27 15:42
加载中...