CH2501 矩阵距离

描述

给定一个N行M列的01矩阵 A，\(A[i][j]\) 与 \(A[k][l]\) 之间的曼哈顿距离定义为：

\(dist(A[i][j],A[k][l])=|i-k|+|j-l|\)

输出一个N行M列的整数矩阵B，其中：

\(B[i][j]=min(1 \le x \le N,1 \le y \le M,A[x][y]=1)⁡{dist(A[i][j],A[x][y])}\)

即求与每个位置曼哈顿距离最近的1

\(N,M \le 1000\)。

输入格式

第一行两个整数N,M。

接下来一个N行M列的01矩阵，数字之间没有空格。

输出格式

一个N行M列的矩阵B，相邻两个整数之间用一个空格隔开。

样例输入

样例输出

思路

有没有觉得，有点像洪水填充？

假设只有一个1，我们可以用广搜来实现。因为每次搜下一个位置，距离都会+1，所以队列里元素距起始点的距离是单调递增的。因此，当我们搜到一个没有被搜到的位置，直接记录最优答案即可。

但是这里有好几个1。不过这也无妨，我们把这几个1的ans初始值标记为0，把它们都push进队列，然后广搜即可。原理十分简单。

代码

#include<bits/stdc++.h>

using namespace std;

#define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout )

#define MAXN 1005

int N, M;

bool a[MAXN][MAXN];

int ans[MAXN][MAXN];

queue<int> Qx, Qy;

char t;

int dir[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 };

int main(){

	memset( ans, -1, sizeof ans );

	scanf( "%d%d", &N, &M );

	for ( int i = 1; i <= N; ++i )

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

			while( ( t =  getchar() ) != '1' && t != '0' );

			a[i][j] = t ^ '0'; if ( a[i][j] ) Qx.push(i), Qy.push(j), ans[i][j] = 0;

		}

	int x, y, tx, ty;

	while( !Qx.empty() ){

		x = Qx.front(); y = Qy.front(); Qx.pop(); Qy.pop();

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

			tx = x + dir[i][0]; ty = y + dir[i][1];

			if ( tx > 0 && ty > 0 && tx <= N && ty <= M && ans[tx][ty] == -1 ){

				ans[tx][ty] = ans[x][y] + 1; Qx.push(tx); Qy.push(ty);

			}

		}

	}

	for ( int i = 1; i <= N; ++i, putchar('\n') )

		for ( int j = 1; j <= M; ++j )

			printf( "%d ", ans[i][j] );

	return 0;

}

巴特西

「CH2501」矩阵距离解题报告

CH2501 矩阵距离

描述

输入格式

输出格式

样例输入

样例输出

思路

代码

最新文章

热门文章

巴特西

「CH2501」 矩阵距离 解题报告

CH2501 矩阵距离

描述

输入格式

输出格式

样例输入

样例输出

思路

代码

最新文章

热门文章

「CH2501」矩阵距离解题报告