リンク

質問リンク

問題の説明

宝島の地図を発見した後、フック船長は宝物を探し始めた.宝島地図は下図のように矩形で、複数の格に分かれています.各マスは陸地(L)または海洋(W)で表される.この地図では、移動は上下左右に隣接する陸地でしかできず、1マス移動には1時間かかります.宝は互いに最短距離を移動するのに最も長い陸地に埋め込まれている.2つの陸地を表す場所の間を最短距離に移動するには、同じ場所を2回以上歩いたり、遠回りしたりしてはいけません.

例えば、上記のような地図があれば、宝物は下に表示されている2つの場所に埋もれ、この2つの間の最短距離までの時間は8時間になります.

蔵宝図を取得するときは、蔵宝の場所間の最短距離を求めるプログラムを作成してください.

入力

1行目では、蔵宝図の縦の大きさと横の大きさがスペースを隔てています.次に、LとWが表示された蔵宝図は以下の通りで、各文字の間にスペースはありません.蔵宝図の横、縦の寸法はそれぞれ50以下です.

しゅつりょく

出力は1行目の埋蔵宝物の2つの場所の間で最短距離に移動する時間である.

I/O例

に答える

題の中で、質問の最終は最も遠い2つのLです.

LのすべてのLでbfsが実行されると、copymapが+1回更新され、最大値が記録されるたびに返されます.

の2回のコースで得られた値のうち、最大の値を見つければ

です.
問題は本当に簡単ですが、ちょっと回ってしまいました.ははは
最初に,出力距離の最大値の1つとしてLの2つの組合せLを用いて,非常に非効率なアルゴリズムを記述した.
そしてタイムアウトされて考え直したのですが...ドアで解けると思ったので、試してみたら、よかった!ははは

コード#コード#

package Sample;
import java.util.*;
class Point {
	int x, y;
	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
public class Main {
	static ArrayList<Point> landtemp = new ArrayList<>();
	static Point[] land;
	static int[][] map;
	static int[][] copymap;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	public static int bfs(Point start, int row, int col) {
		Queue<Point> q = new LinkedList<>();
		boolean[][] visited = new boolean[row][col];
		q.add(start);
		visited[start.x][start.y] = true;
		copymap = new int[row][col];
		for(int x = 0; x < row; x++)
			for(int y = 0; y < col; y++)
				copymap[x][y] = map[x][y];
		int max = -1;
		while(!q.isEmpty()) {
			Point now = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				
				if(nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
				if(!visited[nx][ny] && copymap[nx][ny] > 0) {
					visited[nx][ny] = true;
					copymap[nx][ny] = copymap[now.x][now.y] + 1;
					q.add(new Point(nx, ny));
					if(max < copymap[nx][ny])
						max = copymap[nx][ny];
				}
			}
		}
		return max - 1;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int row = sc.nextInt();
		int col = sc.nextInt();
		map = new int[row][col];
		
		for(int i = 0; i < row; i++) {
			String s = sc.next();
			for(int j = 0; j < s.length(); j++) {
				if(s.charAt(j) == 'W') {
					map[i][j] = 0;
				}
				else {
					map[i][j] = 1;
					landtemp.add(new Point(i, j));
				}
			}
		}
		land = (Point[]) landtemp.toArray(new Point[landtemp.size()]);
		int answer = 0;
		for(int i = 0; i < land.length; i++) {
			int temp = bfs(land[i], row, col);
			if(answer < temp)
				answer = temp;
		}
		System.out.println(answer);
	}
}