为什么一直68
查看原帖
为什么一直68
138106
tgs9311楼主2021/11/28 23:20

改了好多遍还是68

bfs+deque

#include<bits/stdc++.h>
#include<bits/extc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
namespace FAST_IO
{
	template<typename T> void read(T &a)
	{
		a=0;
		int f=1;
		char c=getchar();
		while(!isdigit(c))
		{
			if(c=='-')
			{
				f=-1;
			}
			c=getchar();
		}
		while(isdigit(c))
		{
			a=a*10+c-'0';
			c=getchar();
		}
		a=a*f;
	}
	template<typename T> void read(T &a,T &b ...)
	{
		read(a);
		read(b);
	}
	template <typename T> void write(T a)
	{
		if(a<0)
		{
			a=-a;
			putchar('-');
		}
		if(a>9)
		{
			write(a/10);
		}
		putchar(a%10+'0');
	}
	template<typename T> void write(T &a,T &b ...)
	{
		write(a);
		putchar(' ');
		wirte(b);
	}
	template <typename T> void writeln(T a)
	{
		write(a);
		puts("");
	}
	template<typename T> void writeln(T &a,T &b ...)
	{
		write(a);
		puts("");
		wirte(b);
	}
}
const int maxn=502*502;
int n,m;
vector<pair<int,int> > g[maxn];
int getpos(int x,int y)
{
	return (x-1)*(m+1)+y;
}
int vis[maxn],flag;
void bfs()
{
	deque<pair<int,int> > q;
	q.push_back(make_pair(getpos(1,1),0));
	while(q.size())
	{
		int from=q.front().first,now=q.front().second;		
		if(from==getpos(n+1,m+1))
		{
			flag=true;
			cout<<now;
			return;
		}
		q.pop_front();
		for(int i=0;i<g[from].size();i++)
		{
			int to=g[from][i].first,len=g[from][i].second;

			if(vis[to])
			{
				continue;
			}
			if(!len)
			{
				q.push_front(make_pair(to,now));	
			}
			else
			{
				q.push_back(make_pair(to,now+1));
			}
			vis[to]=true;				
		}
	}
}
int main()
{
	//1,1~n+1,m+1
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char c;
			cin>>c;
			int from=getpos(i,j),to=getpos(i+1,j+1);
			int afrom=getpos(i,j+1),ato=getpos(i+1,j);
			//cout<<from<<" "<<to<<endl; 
			if(c=='\\')
			{
				g[to].push_back(make_pair(from,0));
				g[from].push_back(make_pair(to,0));
				g[afrom].push_back(make_pair(ato,1));
				g[ato].push_back(make_pair(afrom,1));
			}
			if(c=='/')
			{
				g[ato].push_back(make_pair(afrom,0));
				g[afrom].push_back(make_pair(ato,0));
				g[from].push_back(make_pair(to,1));
				g[to].push_back(make_pair(from,1));				
			}
		}
	}
	bfs();	
	if(flag)
	{
		return 0;
	}
	cout<<"NO SOLUTION";
}


2021/11/28 23:20
加载中...