bfs 20pts,求调
查看原帖
bfs 20pts,求调
754502
_AyachiNene楼主2023/6/1 15:16
#include<bits/stdc++.h>
using namespace std;
char a[114][514];
int w,h,sx,sy,vis[114][514];
queue<pair<int,pair<int,int> > >q;
void bfs()
{
	q.push(make_pair(0,make_pair(sx,sy)));
	for(int i=sx-1;i>=1;i--)
	{
		if(a[i][sy]=='*')
			break;
		q.push(make_pair(0,make_pair(i,sy)));
	}
	for(int i=sx+1;i<=w;i++)
	{
		if(a[i][sy]=='*')
			break;
		q.push(make_pair(0,make_pair(i,sy)));
	}
	for(int i=sy-1;i>=1;i--)
	{
		if(a[sx][i]=='*')
			break;
		q.push(make_pair(0,make_pair(sx,i)));
	}
	for(int i=sy+1;i<=h;i++)
	{
		if(a[sx][i]=='*')
			break;
		q.push(make_pair(0,make_pair(sx,i)));
	}
//	while(!q.empty())
//	{
//			int x=q.front().second.first;
//		int y=q.front().second.second;
//		int w=q.front().first;
//		q.pop();
//				cout<<x<<" "<<y<<" "<<w<<endl;
//	}
	while(!q.empty())
	{
		int x=q.front().second.first;
		int y=q.front().second.second;
		int w=q.front().first;
		q.pop();
		if(vis[x][y])
			continue;
		vis[x][y]=1;
//		cout<<x<<" "<<y<<" "<<w<<endl;
		if(a[x][y]=='C'&&(x!=sx||y!=sy))
		{
			cout<<w;
			return;
		}
		for(int i=x-1;i>=1;i--)
		{
			if(a[i][y]=='*')
				break;
			q.push(make_pair(w+1,make_pair(i,y)));
		}
		for(int i=x+1;i<=w;i++)
		{
			if(a[i][y]=='*')
				break;
			q.push(make_pair(w+1,make_pair(i,y)));
		}
		for(int i=y-1;i>=1;i--)
		{
			if(a[x][i]=='*')
				break;
			q.push(make_pair(w+1,make_pair(x,i)));
		}
		for(int i=y+1;i<=h;i++)
		{
			if(a[x][i]=='*')
				break;
			q.push(make_pair(w+1,make_pair(x,i)));
		}
	}
}
int main()
{
	cin>>h>>w;
	for(int i=1;i<=w;i++)
		for(int j=1;j<=h;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='C')
				sx=i,sy=j;
		}
	bfs();
//	for(int i=1;i<=w;i++)
//	{
//		for(int j=1;j<=h;j++)
//			cout<<vis[i][j]<<" ";
//		cout<<endl;
//	}
}
2023/6/1 15:16
加载中...