[Algorithm] 🥗白飯を避ける

0、問題

コレスコアパート8階は学生たちが3食を解決する空間だ.しかし、良心のない学生の野蛮な行為のため、食べ物は通路の真ん中に落ちた.これらの食べ物は近くのものに囲まれて、大きな食べ物のゴミになっています.
この問題を出した先生個人は本当にこれらの食べ物を室内の靴に埋めるのが嫌いです.ちなみに、私たちが要求した答えはこの問題を出す助教ではありません.
通路に落ちた食べ物を避けるのは容易なことではない.だから、先生は落ちた食べ物の中で一番大きい食べ物を避けたいだけです.
先生に最大の食べ物の大きさを手伝って、「10 ra」と呼ばないでください.
入力
第1行は、通路の長手方向長さN(1≦N≦100)および横方向長さM(1≦M≦100)および食物ゴミの個数K(1≦K≦10000)を与える.次に、次のK線直線上に食べ物が落ちる座標(r,c)を与える.
座標(r,c)のrは上から下,cは左から下を基準とする.
しゅつりょく
最初の行の出力食品の中で最大の食べ物の大きさです.

1.アイデア

💡 DFS
💡 しょくぶつごみ
💡 配列全体でごみの位置を選択し,上下左右にごみがある場合にcountを行い,ごみの位置に移動する.
💡 ごみの位置が連続していない場合は、配列全体を返して参照し、ごみの位置を検索し、上のコードを繰り返します.

2.コア解答

1)食品ごみの所在地表示

for(int i=0; i<k; i++) {
	s = br.readLine().split(" ");
	map[Integer.parseInt(s[0])][Integer.parseInt(s[1])] = trash;
}

2)全体の並びからゴミがある場所を選び、上下左右にゴミがある場合はカウントし、ゴミがある場所に移動します.

for(int i=0; i<4; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
			
	if(nx < 1 || ny < 1 || nx>=n+1 || ny>=m+1)
		continue;
			
	if(!visited[nx][ny] && map[nx][ny] == trash) {
		visited[nx][ny] = true;
		dfs(nx,ny);
	}
}

3)ゴミの位置が連続していない場合は、配列全体に戻り、ゴミの位置を見つけ、上のコードを繰り返します.

for(int i=1; i<n+1; i++) {
	for(int j=1; j<m+1; j++) {
		if(map[i][j] == trash) {
			visited[i][j] = true;
			dfs(i,j);
			max = Math.max(count, max);
			count = 0;
		}
	}
}

3.コード

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;
import java.util.ArrayList;

public class Bruteforce_7 {
	static final int trash = 1;
	static int n,m,k, count = 0;
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		
		n = Integer.parseInt(s[0]);
		m = Integer.parseInt(s[1]);
		k = Integer.parseInt(s[2]);
		
		map = new int[n+1][m+1];
		visited = new boolean[n+1][m+1];
		
		for(int i=0; i<k; i++) {
			s = br.readLine().split(" ");
			map[Integer.parseInt(s[0])][Integer.parseInt(s[1])] = trash;
		}
		
		int max = 0;
		for(int i=1; i<n+1; i++) {
			for(int j=1; j<m+1; j++) {
				if(map[i][j] == trash) {
					visited[i][j] = true;
					dfs(i,j);
					max = Math.max(count, max);
					count = 0;
				}
			}
		}
		
		System.out.println(max);
		
	}
	
	public static void dfs(int x, int y) {
		count++;
		
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx < 1 || ny < 1 || nx>=n+1 || ny>=m+1)
				continue;
			
			if(!visited[nx][ny] && map[nx][ny] == trash) {
				visited[nx][ny] = true;
				dfs(nx,ny);
			}
		}
	}

}

4.結果

成功