笔试题:水陆距离

avatar

水陆距离
时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述
给定一个N x M的01矩阵,其中1表示陆地,0表示水域。对于每一个位置,求出它距离最近的水域的距离是多少。

矩阵中每个位置与它上下左右相邻的格子距离为1。

输入
第一行包含两个整数,N和M。

以下N行每行M个0或者1,代表地图。

数据保证至少有1块水域。

对于30%的数据,1 <= N, M <= 100

对于100%的数据,1 <= N, M <= 800

输出
输出N行,每行M个空格分隔的整数。每个整数表示该位置距离最近的水域的距离。

样例输入

4 4  
0110  
1111  
1111  
0110

样例输出

0 1 1 0  
1 2 2 1  
1 2 2 1  
0 1 1 0

BFS 宽度优先搜索

import java.util.*;
 
public class Main  {
	static class Node{
		int x;
		int y;
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}final static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		String a[] = new String[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.next();
		}
 
		int[][] ans = new int[n][m];
		for (int i = 0; i < n; i++) {
			Arrays.fill(ans[i], -1);
		}
		Queue<Node> que = new LinkedList();
 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (a[i].charAt(j) == '0') {
					ans[i][j] = 0;
					que.add(new Node(i, j));
				}
			}
		}
 
		while (que.peek() != null) {
			Node node = que.poll();
			for (int i = 0; i < 4; i++) {
				int x = node.x;
				int y = node.y;
				int nx = x + dir[i][0];
				int ny = y + dir[i][1];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
					continue;
				}
				if (ans[nx][ny] == -1 || ans[nx][ny] > ans[x][y] + 1) {
					ans[nx][ny] = ans[x][y] + 1;
					que.add(new Node(nx, ny));
				}
			}
		}
 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				System.out.print(ans[i][j] + " ");
			}
 
			System.out.println();	
		}
	}
}
目前还没有回答,快来帮帮TA吧!
添加一条评论 请尽量发布对他人有帮助的评论

登录后可发布评论

登录 | Github登录