priority_queue + bfs 98pts 求调
查看原帖
priority_queue + bfs 98pts 求调
722018
User722018楼主2024/7/24 11:43
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#define ll long long
#define sort stable_sort
using namespace std;
int n,m;
struct node
{
	int u,v,w,to;
}q[1100510];
int kkk(int x,int y)
{
	int z=0;
	z=x*1000;
	z+=y;
	return z;
}
int first[500510];
int vis[510510];
int jl[510510];
int tot=0;
void add_edge(int u,int v,int w)
{
	tot++;
	q[tot].u=u;
	q[tot].v=v;
	q[tot].w=w;
	q[tot].to=first[u];
	first[u]=tot;
}
struct Node
{
	int x,time;
	bool operator <(const Node &a) const
	{
		return time > a.time;
	}
};
priority_queue <Node> que;
int bbfs()
{
	Node abc;
	abc.x=kkk(1,1);
	abc.time=0;
	que.push(abc);
	vis[kkk(1,1)]=1;
	int ans=1e9;
	while(!que.empty())
	{
		Node z=que.top();
		que.pop();
		if(z.time>=jl[z.x])
		{
			continue;
		}
		jl[z.x]=min(jl[z.x],z.time);
//		cout<<z.x<<" "<<z.time<<endl;
		if(z.x==kkk(n+1,m+1))
		{
			ans=min(ans,z.time);
			continue;
		}
		int k=first[z.x];
		while(k)
		{
//			if(vis[q[k].v]!=0)
//			{
//				k=q[k].to;
//				continue;
//			}
			Node c;
			c.x=q[k].v;
			c.time=z.time+q[k].w;
			que.push(c);
//			cout<<"--"<<c.x<<" "<<c.time<<endl;
			vis[q[k].v]=z.time+q[k].w;
			k=q[k].to;
		}
	}
	if(ans==1e9)
	{
		return -1;
	}
	return ans;
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<=510509;i++)
	{
		jl[i]=1e9; 
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char c;
			cin>>c;
			if(c=='\\')
			{
				add_edge(kkk(i,j),kkk(i+1,j+1),0);
				add_edge(kkk(i+1,j+1),kkk(i,j),0);
				add_edge(kkk(i,j+1),kkk(i+1,j),1);
				add_edge(kkk(i+1,j),kkk(i,j+1),1);
			}
			if(c=='/')
			{
				add_edge(kkk(i,j),kkk(i+1,j+1),1);
				add_edge(kkk(i+1,j+1),kkk(i,j),1);
				add_edge(kkk(i,j+1),kkk(i+1,j),0);
				add_edge(kkk(i+1,j),kkk(i,j+1),0);
			}
		}
	}
//	for(int i=1;i<=tot;i++)
//	{
//		cout<<q[i].u<<" "<<q[i].v<<" "<<q[i].w<<endl;
//	}
	if((n+m)%2==1)
	{
		cout<<"NO SOLUTION"<<endl;
		return 0;
	}
//	for(int i=1;i<=tot;i++)
//	{
//		cout<<q[i].u<<" "<<q[i].v<<" "<<q[i].w<<" "<<q[i].to<<endl;
//	}
	int ans=bbfs();
	if(ans==-1)
	{
		cout<<"NO SOLUTION"<<endl;
		return 0;
	}
	cout<<ans<<endl;
	return 0;
}
2024/7/24 11:43
加载中...