2021.10.29 P1649 [USACO07OCT]Obstacle Course S（BFS）

题意：

给一张n*n的图，起点为A，终点为 B，求从A到B转弯次数最少为多少。

分析：

是否存在路径用DFS，最短路径或最长路径用BFS。只不过先现在需要把以前距离小的放前面改为转弯次数少的放前面，类似于最短路。

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int N=110;

int n,startx,starty,endx,endy,a[N][N],vis[N][N][5];

int disx[5]={0,0,0,-1,1},disy[5]={0,1,-1,0,0};

struct node{

	int x,y,change,flag;

	bool operator <(const node &b)const{

		return change>b.change;

	}

};

inline void bfs(){

	priority_queue<node>q;

	vis[startx][starty][1]=vis[startx][starty][2]=vis[startx][starty][3]=vis[startx][starty][4]=1;

	q.push({startx,starty,0,1});

	q.push({startx,starty,0,2});

	q.push({startx,starty,0,3});

	q.push({startx,starty,0,4});

	while(!q.empty()){

		node tmp=q.top();q.pop();

		//cout<<tmp.x<<" "<<tmp.y<<" "<<tmp.change<<" "<<tmp.flag<<endl;

		for(int i=1;i<=4;i++){

			int xi=tmp.x+disx[i],yi=tmp.y+disy[i];

			int flagi=i,changei=(tmp.flag==i?tmp.change:tmp.change+1);

			//if(xi<1||xi>n||yi<1||yi>n||a[xi][yi]||vis[xi][yi][flagi])continue;

			while(xi<=n&&xi>=1&&yi<=n&&yi>=1&&!a[xi][yi]&&!vis[xi][yi][flagi]){

				vis[xi][yi][flagi]=1;

				q.push({xi,yi,changei,flagi});

				if(xi==endx&&yi==endy){

					cout<<changei-1;

					exit(0);

				}

				xi+=disx[i];yi+=disy[i];

			}

		}

	}

	return ;

}

int main(){

	cin>>n;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++){

			char x;

			cin>>x;

			if(x=='x')a[i][j]=1;

			else if(x=='A')startx=i,starty=j;

			else if(x=='B')endx=i,endy=j;

		}

	}

	bfs();

	cout<<"-1";

	return 0;

}

巴特西

2021.10.29 P1649 [USACO07OCT]Obstacle Course S（BFS）

2021.10.29 P1649 [USACO07OCT]Obstacle Course S（BFS）

最新文章

热门文章