88分被卡常求调
查看原帖
88分被卡常求调
876418
HHYQ_07楼主2023/8/31 22:17
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,v[N][N];
const int dx1[4]={1,-1,-1,1},dy1[4]={1,1,-1,-1};
const int dx2[4]={0,-1,-1,0},dy2[4]={0,0,-1,-1};
char a[N][N];
const char f[5]="\\/\\/";
struct node
{
	int x,y;
}s;
deque<node>q;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>a[i][j];
	if((n+m)&1)
	{
		cout<<"NO SOLUTION";
		return 0;
	}
	memset(v,0x3f,sizeof(v));
	v[0][0]=0;
	q.push_front((node){0,0});
	while(!q.empty())
	{
		s=q.front();q.pop_front();
		for(int i=0;i<4;i++)
		{
			int xx1=s.x+dx1[i];
			int yy1=s.y+dy1[i];
			int xx2=s.x+dx2[i];
			int yy2=s.y+dy2[i];
			if(xx1<0||xx1>n||yy1<0||yy1>m)continue;
			if(f[i]!=a[xx2][yy2])
			{
				int sum=v[s.x][s.y]+1; 
				if(sum<v[xx1][yy1])
				{ 
					q.push_back((node){xx1,yy1}); 
					v[xx1][yy1]=sum; 	
				}
			}	
			else
			{
				int sum=v[s.x][s.y];
				if(sum<v[xx1][yy1])
				{ 
					q.push_back((node){xx1,yy1}); 
					v[xx1][yy1]=sum;	
				}
			}
		}
	}
	cout<<v[n][m];
	return 0;
}

剩下的都 T 了。

2023/8/31 22:17
加载中...