[数据结构与算法]ABC-Bishop2-(bfs和distra的区别)

E

题意：
就是给你一个矩阵，有的能走有的不行，现在问你从起点走到终点的最少次数。每次可以往四个角走，可以走任意距离。

思考：
一看能走任意距离就是洪流的那道题，但是刚开始我想傻逼了，在想中间如果有#怎么判，其实第一次遇到#就可以break了。然后我就写了，我想着走的方向都是不一样的，反正能进来就进来就行了，然后第一次遇到终点就return距离，就错了。因为我用的是一次一次走的，不是枚举多少，所以queue里面不满足单调性了，如果用洪流的话，第一次进来的肯定是最好的，所以同方向的时候不会被更新第二次。但是我习惯写那种distra类型的搜索，所以是贪心或者dp去迭代更新。总之呢，标准的bfs就是每次把能拿到的全部放进来保证队列的单调性，distra呢就是拿进来的会多次迭代更新。并且值得注意的是，明显知道不同的方向会影响答案，所以dist一般都要多维护一维啊，就和维护血量一样，不知道当时比赛的时候想的啥…

代码：

distra做法：

struct node{
	int x,y;
	int dis;
	int op;
	bool operator<(const node&A)const{
		return A.dis<dis;
	}
};

int T,n,m,k;
int stx,sty,edx,edy;
char va[M][M];
int dist[5][M][M];
int dx[4] = {1,1,-1,-1};
int dy[4] = {1,-1,1,-1};
int dir[4] = {1,2,3,4};

void bfs()
{	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=4;k++)
			dist[k][i][j] = inf;
		}
	}
	priority_queue<node> q;
	q.push(node{stx,sty,0,0}); //放进来
	for(int i=1;i<=4;i++) dist[i][stx][sty] = 0;
	while(q.size())
	{
		auto now = q.top();
		q.pop();
		int x = now.x,y = now.y,dis = now.dis,op = now.op;
		if(dis>dist[op][x][y]) continue; //这样去更新就没有意义了
		for(int i=0;i<4;i++)
		{
			int xx = x+dx[i],yy = y+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&va[xx][yy]=='.')
			{
				int nowdis = dis+(op!=dir[i]);
				if(nowdis<dist[dir[i]][xx][yy])
				{
					dist[dir[i]][xx][yy] = nowdis;
					q.push(node{xx,yy,nowdis,dir[i]});
				}
			}
		}
	}
}

signed main()
{
	IOS;
	cin>>n;
	cin>>stx>>sty>>edx>>edy;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		cin>>va[i][j];
	}
	bfs();
	int minn = inf;
	for(int i=1;i<=4;i++) minn = min(minn,dist[i][edx][edy]); //终点的所有方向里取个最小值
	if(minn==inf) cout<<-1;
	else cout<<minn;
	return 0;
}

标准bfs：

int T,n,m,k;
int stx,sty,edx,edy;
char va[M][M];
int dist[M][M];
int vis[4][M][M];
int dx[4] = {1,1,-1,-1};
int dy[4] = {1,-1,1,-1};

void bfs()
{
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dist[i][j] = inf;
	queue<PII> q;
	q.push({stx,sty});
	dist[stx][sty] = 0;
	while(q.size())
	{
		auto now = q.front();
		q.pop();
		int x = now.fi,y = now.se;
		for(int i=0;i<4;i++)
		{
			for(int j=1;;j++)
			{
				int xx = x+j*dx[i],yy = y+j*dy[i];
				if(xx<1||xx>n||yy<1||yy>n||va[xx][yy]=='#') break;
				if(vis[i][xx][yy]) break; //如果这个方向走过了就不看了,vis也就是多加一维罢了
				vis[i][xx][yy] = 1;
				dist[xx][yy] = min(dist[xx][yy],dist[x][y]+1);
				q.push({xx,yy});
			}
		}
	}
}

signed main()
{
	IOS;
	cin>>n;
	cin>>stx>>sty>>edx>>edy;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		cin>>va[i][j];
	}
	bfs();
	if(dist[edx][edy]==inf) cout<<-1;
	else cout<<dist[edx][edy];
	return 0;
}

总结：
多多思考。