リンク

氷山

質問する

地球温暖化で北極氷山が溶けている.図1に示すように、氷山を2次元アレイに表示します.氷山の各部分の高さ情報は,配列された各セルに正の整数として格納される.氷山以外の海に対応する格には0が格納されている.図1では、スペースはすべてゼロで埋め込まれていると思います.

氷山の高さは海水との接触が多い場所でより速く減少するため、配列中の氷山の各部分に対応する格子の高さは毎年、格子の中で東西南北4方向に付着する0の格子の個数を減少させる.ただし、各セルに格納される高さは0より小さくなりません.海水は湖水のように氷山に囲まれているかもしれない.従って、図1の氷山は、図2に示すように1年後に変形する.
図3は、図1の氷山の2年後の変化を示す.2 D配列では,東西南北方向の格子が互いに接続されている.したがって、図2の氷山は1つであり、図3の氷山は3つに分かれている.

氷山が1つ与えられた場合、プログラムを作成して、この氷山が2つ以上分離された最初の時間(年)を求めます.図1の氷山について、答えは2です.全てが溶けるまで2つ以上離さないと、プログラムは0を出力します.

入力

1行目では、2つの整数NとMは、2次元配列の行数と列数を表すスペースで区切られます.NとMは3以上300以下である.次のN行では、各行の間にスペースがあり、M個の整数は配列の各行を表します.各グリッドの値は0以上10以下です.配列では、氷山が占める格の個数、すなわち1以上の整数が占める格の個数が10000以下である.配列の最初の行と最後の行と最後の列は常に0で埋め込まれます.

しゅつりょく

1行目は氷山分離の最初の時間(年)を出力する.氷山が溶けるまで分離していない場合は0を出力します.

に答える

最も重要な関数はmilt()関数とseparate()関数です.

public static int SeparateNum()
	{
		boolean[][] visited=new boolean[n][m];
		int cnt=0;
		
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<m; j++)
			{
				if(map[i][j]!=0 && !visited[i][j])
				{
					DFS(i,j,visited);
					cnt++;
				}
			}
		}
		
		return cnt;
	}
	
	public static void DFS(int x, int y, boolean[][] visited)
	{
		visited[x][y]=true;
		
		for(int i=0; i<4; i++)
		{
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			if(nx < 0 || nx >=n || ny<0 || ny>=m)
				continue;
			
			if(map[nx][ny]!=0 && !visited[nx][ny])
				DFS(nx, ny, visited);
		}
	}
    

この関数は氷山を数える関数です.
separatenum関数にfor文がなくmapが0でない場合
接続された部分がすべてtrueになるようにdfs関数を再度呼び出します.

	public static void Melt()
	{
		Queue<IceBerg> q=new LinkedList<>();
		
		boolean visited[][]=new boolean[n][m];
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<m; j++)
			{
				if(map[i][j]!=0)
				{
					q.offer(new IceBerg(i, j));
					visited[i][j]=true;
				}
			}
		}
		
		while(!q.isEmpty())
		{
			IceBerg ice=q.poll();
			int seanum=0;
			
			for(int i=0; i<4; i++)
			{
				int nx=ice.x+dx[i];
				int ny=ice.y+dy[i];
				
				if(nx<0 || nx>=n || ny<0 || ny>=m)
					continue;
				
				if(!visited[nx][ny] && map[nx][ny]==0)
					seanum++;
			}
			
			if(map[ice.x][ice.y]-seanum < 0)
				map[ice.x][ice.y]=0;
			else
				map[ice.x][ice.y]-=seanum;
			
		}
	}

溶融関数の最も重要な点はブールアクセス配列である.これは.
重要な原因は、問題の中で、各氷山が1年の融解過程で氷山がゼロであれば、この0は他の氷山にも影響を与えることだ.問題は、その年に溶けた氷山が他の氷山に影響を及ぼさないようにアクセス配列を設け、その氷山の位置が他の氷山に影響を及ぼさないようにすることです!

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;

class IceBerg{
	int x;
	int y;
	
	IceBerg(int x, int y)
	{
		this.x=x;
		this.y=y;
	}
}

public class practice {
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	static int n,m;
	static int map[][];
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		int ans=0;
		int cnt=0;
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		
		map=new int[n][m];
		for(int i=0; i<n; i++)
		{
			st=new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++)
			{
					map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		while((cnt=SeparateNum()) < 2)
		{
			if(cnt==0)
			{
				ans=0;
				break;
			}
			
			Melt();
			ans++;
		}
		
		System.out.println(ans);
	
	}
	
	public static int SeparateNum()
	{
		boolean[][] visited=new boolean[n][m];
		int cnt=0;
		
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<m; j++)
			{
				if(map[i][j]!=0 && !visited[i][j])
				{
					DFS(i,j,visited);
					cnt++;
				}
			}
		}
		
		return cnt;
	}
	
	public static void DFS(int x, int y, boolean[][] visited)
	{
		visited[x][y]=true;
		
		for(int i=0; i<4; i++)
		{
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			if(nx < 0 || nx >=n || ny<0 || ny>=m)
				continue;
			
			if(map[nx][ny]!=0 && !visited[nx][ny])
				DFS(nx, ny, visited);
		}
	}
	
	public static void Melt()
	{
		Queue<IceBerg> q=new LinkedList<>();
		
		boolean visited[][]=new boolean[n][m];
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<m; j++)
			{
				if(map[i][j]!=0)
				{
					q.offer(new IceBerg(i, j));
					visited[i][j]=true;
				}
			}
		}
		
		while(!q.isEmpty())
		{
			IceBerg ice=q.poll();
			int seanum=0;
			
			for(int i=0; i<4; i++)
			{
				int nx=ice.x+dx[i];
				int ny=ice.y+dy[i];
				
				if(nx<0 || nx>=n || ny<0 || ny>=m)
					continue;
				
				if(!visited[nx][ny] && map[nx][ny]==0)
					seanum++;
			}
			
			if(map[ice.x][ice.y]-seanum < 0)
				map[ice.x][ice.y]=0;
			else
				map[ice.x][ice.y]-=seanum;
			
		}
	}
}

ブログ参照