signed

QiShunwang

“诚信为本、客户至上”

软件学院3.14天梯模拟 L3-1 桥短几何 (30 分)(BFS,DFS,连通块,多源最短路,多源BFS)

2021/3/21 1:10:39   来源:

在一个NxN的布尔矩阵中,0表示水,1表示陆地,一片由1围成的最大区域就是一个岛,假定方阵中有且只有两个岛,请计算连接这两个岛的最短的桥的长度(架桥相当于翻转0为1,使两个岛相连)。

输入样例1:

第一行一个正整数N(取值范围在[2--100])。 以后N行以空格分隔的0或1,每行N个(0表示水,1表示陆地)。

3
0 0 1
0 0 1
1 1 0

输出样例1:

一个表示最短的桥的长度的正整数,本例中,正中间或右下角均是可行方案。

1

输入样例2:

第一行一个正整数N(取值范围在[2--100])。 以后N行以空格分隔的0或1,每行N个(0表示水,1表示陆地)。

5
1 1 1 1 1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 1

输出样例2:

一个表示最短的桥的长度的正整数,本例中,最后一行是可行方案。

3

思路: 

首先我们要做到区分两个岛,那怎么区分呢?

通过连通块,因为两个岛都被标记成了1,但两个岛分别属于两个不同的连通块,所以我们可以通过求解连通块去将其中一个岛的标记从1修改为其他的数字(这里我修改成了2)

求连通块,BFS,DFS都行,这里我用DFS,代码会简洁一些

void dfs(int x , int y)                 //从一个岛的任意一点出发
{
	G[x][y] = 2;                        //每到一个点都把自身标记为2
	for(int i = 0 ; i < 4 ; i++)        //再向上下左右四个方向去拓展
	{
		int tx = x + dx[i][0] , ty = y + dx[i][1];
		if(tx >= 0 && tx < n && ty >= 0 && ty < n && G[tx][ty] == 1)    //保证不越界,并且是岛内的点
			dfs(tx , ty); 
	}
}

标记完连通块,剩下就是求两个连通块的最短路径了

我们先看问题的类型,由于都是连通块,所以,起点和终点都是有一个或多个的

那么类型就属于多源最短路

那么很容易想到Floyd算法,我们再看复杂度,n<=100,1s最多执行10^{7}~10^{8},那么我们最多可以使用O(n^{4}),而Floyd算法的复杂度是O(n^{3})是可行的

但是Floyd算法是需要有边的存在的,而这道题没有边,但是两点之间的距离也很简单能过算出,比如有两个点A,B,A点的坐标是(x1 , y1),B点的坐标是(x2 , y2)

那么AB两点的距离dist = \left | x1 - x2 \right | + \left | y1 - y2 \right | - 1

我们可以通过枚举两个岛上的点的坐标计算两点之间的最短距离,每次计算取最小值,最后就是两个岛的最短距离了

int ans = 210;                    //初始化答案为最大距离
for(int a = 0 ; a < n ; a++)
{
    for(int b = 0 ; b < n ; b++)
    {
        for(int c = 0 ; c < n ; c++)
        {
            for(int d = 0 ; d < n ; d++)      //通过四层循环来枚举两个点的坐标A(a,b),B(c,d)
            {
                if(G[a][b] + G[c][d] == 3)    //判断两个点是否来自两个岛,只有2 + 1才能得到3
                    ans = min(ans , abs(a - c) + abs(b - d) - 1);//每次和最终答案取最小值
            }
        }
    }
}

同样,这题也可以通过多源BFS来做,多源BFS和普通的BFS差别就在,多源BFS初始队列有一个或多个元素,而普通BFS初始队列仅有一个元素(可以理解为多源BFS是有一个超级源点,该超级源点到某些点的距离为0,那么BFS一次就会把这些点都入队)

我们可以在求解连通块的同时,把同一个岛的点都入队

然后再进行BFS拓展,第一次拓展到其他岛的点所消耗的步数就是两个岛的最短距离

int bfs()
{
	while(q.size())
	{
		auto t = q.front();
		q.pop();
		
		for(int i = 0 ; i < 4 ; i++)
		{
			int tx = t.x + dx[i][0] , ty = t.y + dx[i][1];
			if(tx >= 0 && tx < n && ty >= 0 && ty < n && G[tx][ty] != -1)
			{
				if(G[tx][ty] == 1)    //第一次拓展到其他岛上的点就返回所花费的步数
					return t.step;
				
				G[tx][ty] = -1;       //将该点标记为-1,表示为已经访问,防止重复访问
				q.push({tx , ty , t.step + 1});
			}
		}
	}
}

 代码一(类Floyd算法):

//L3-1 桥短几何 (30 分)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 210;

int n;
int x , y;
int G[N][N];
int dx[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};

void dfs(int x , int y)
{
	G[x][y] = 2;
	q.push({x , y , 0});
	for(int i = 0 ; i < 4 ; i++)
	{
		int tx = x + dx[i][0] , ty = y + dx[i][1];
		if(tx >= 0 && tx < n && ty >= 0 && ty < n && G[tx][ty] == 1)
			dfs(tx , ty); 
	}
}

int main()
{
	cin>>n;
	for(int i = 0 ; i < n ; i++)
	{
		for(int j = 0 ; j < n ; j++)
		{
			cin>>G[i][j];	
			if(G[i][j])
				x = i , y = j;
		}			
	}	
	
	dfs(x , y);
    
    int ans = 210;
    for(int a = 0 ; a < n ; a++)
    {
        for(int b = 0 ; b < n ; b++)
        {
            for(int c = 0 ; c < n ; c++)
            {
                for(int d = 0 ; d < n ; d++)
                {
                    if(G[a][b] + G[c][d] == 3)
                        ans = min(ans , abs(a - c) + abs(b - d) - 1);
                }
            }
        }
    }
	cout<<ans;
	return 0;
}

 代码二(多源BFS):

//L3-1 桥短几何 (30 分)
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 210;

struct Point
{
	int x;
	int y;
	int step;
};

int n;
int x , y;
int G[N][N];
queue<Point> q;
int dx[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};

void dfs(int x , int y)
{
	G[x][y] = 2;
	q.push({x , y , 0});
	for(int i = 0 ; i < 4 ; i++)
	{
		int tx = x + dx[i][0] , ty = y + dx[i][1];
		if(tx >= 0 && tx < n && ty >= 0 && ty < n && G[tx][ty] == 1)
			dfs(tx , ty); 
	}
}

int bfs()
{
	while(q.size())
	{
		auto t = q.front();
		q.pop();
		
		for(int i = 0 ; i < 4 ; i++)
		{
			int tx = t.x + dx[i][0] , ty = t.y + dx[i][1];
			if(tx >= 0 && tx < n && ty >= 0 && ty < n && G[tx][ty] != -1)
			{
				if(G[tx][ty] == 1)
					return t.step;
				
				G[tx][ty] = -1;
				q.push({tx , ty , t.step + 1});
			}
		}
	}
}

int main()
{
	cin>>n;
	for(int i = 0 ; i < n ; i++)
	{
		for(int j = 0 ; j < n ; j++)
		{
			cin>>G[i][j];	
			if(G[i][j])
				x = i , y = j;
		}			
	}	
	
	dfs(x , y);
	cout<<bfs();
	return 0;
}