算法-BFS

• BFS
• • bfs在二维数组
  • • 1. 2021-4-10 十字路口最优解

BFS

bfs在二维数组

1. 2021-4-10 十字路口最优解

题目：

在小美和小团生活的城市中，有n行m列共计n*m个十字路口，第i行j列的十字路口有两个属性aij，b­ij。当行人处在i行j列的路口，对于任意非负整数k:

当时间处在[k x aij+k x b­ij), (k+1) x aij+k x bij)时，行人可以选择走到i±1行j列的路口。

当时间处在[(k+1) x aij+k x bij), (k+1) x aij+(k+1) x b­ij)时，行人可以选择走到i行j±1列的路口。

每次移动花费的时间为1，且要保证将要去的十字路口存在，即属于n*m个路口当中。可以选择原地静止不动。

在第0时刻，小美处在xs行ys列的十字路口处，要去xt行yt列的十字路口找小团。小团原地不动等小美，请问小美所花费的时间最少是多少?

输入描述:

第一行六个正整数n，m，xs，ys，xt，yt，含义如上文所示。以样例第一行【5、5、2、4、4、3】 共计6个数字为例，前两位数字代表有5*5的二维数组，三、四位数字代表小美处在2行4列的十字路口处，五、六位数字代表要去4行3列的十字路口找小团。

接下来n行每行m个正整数，在样例中为第一个5*5的二维数组，第i行第j个数代表i行j列十字路口的属性aij。

接下来n行每行m个正整数，在样例中为第二个5*5的二维数组，第i行第j个数代表i行j列十字路口的属性bij。

对于100%的数据，1≤n，m，xs，ys，xt，yt，aij，bij≤100。

输出描述:

输出1行1个整数代表答案。

示例1

输入

5 5 2 4 4 3
2 1 1 3 1
1 4 2 3 1
4 4 4 2 1
3 1 1 2 4
5 1 5 5 1
5 3 4 1 3
1 1 2 2 2
2 1 4 4 5
1 1 5 3 3
3 2 1 3 3

输出

3

思路：

这道题一开始我使用DFS做的，但是只通过了百分之40的用例。
官方用BFS给我上了一课。
首先官方设了一个Node用来存x和y。
设置了一个directions数组用来存0,-1,1。即移动的三种状态。
以及一个标记数组mark。
cost作为当前已经花费的时间，每一次bfs的循环处理当前cost可能能走的几个位置。
即len=q.size()。
当前cost是x加还是y加由题目判断，即rest=cost%(axy+bxy)，比如axy为2，bxy为5。
那么当rest<2即x加，不然y加。如果当前directions为0，那么也是一种情况。
如果加完以后的x和y是没有访问过的，即!mark ，那么入队作为下一秒的情况。
那么当某一次now.x==xt&&now.y==yt时，cost就可以返回了。

这道题的精髓就是用节点记录了某个点的位置，再通过directions数组来处理它，把每秒可能去的位置入队。

代码：

#include<bits/stdc++.h>
using namespace std;

int n, m, xs, ys, xt, yt;
int a[101][101];
int b[101][101];
vector<int> directions = { 0,-1,1 };
bool mark[101][101];
struct node
{
	int x, y;
	node() {}
	node(int a, int b) :x(a), y(b) {}
};
int bfs()
{
	queue<node> q;
	q.push(node(xs, ys));
	int cost = 0;
	while (q.size() != 0)
	{
		int len = q.size();
		for (int i = 0; i < len; ++i)
		{
			node now = q.front();
			if (now.x == xt && now.y == yt)return cost;
			q.pop();
			mark[now.x][now.y] = true;
			for (int j = 0; j < directions.size(); ++j)
			{
				int x = now.x; int y = now.y;
				if (x<1 || x>n || y<1 || y>m)continue;
				int rest = cost % (a[x][y] + b[x][y]);
				if (rest < a[x][y])
				{
					x += directions[j];
				}
				else
				{
					y += directions[j];
				}
				if (j == 0 || !mark[x][y])
				{
					q.push(node(x, y));
					mark[x][y] = true;
				}
			}	
		}
		cost++;
	}
	return cost;
}
int main()
{
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(mark, 0, sizeof(mark));
	scanf("%d%d%d%d%d%d", &n, &m, &xs, &ys, &xt, &yt);
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &b[i][j]);
		}
	}
	cout << bfs() << endl;
	return 0;
}
}