Untitled

 avatar
unknown
plain_text
2 years ago
1.6 kB
3
Indexable
import java.util.Scanner;

public class Solution {
	static int n, m;
	static int[][] a;
	static int[][] visit;
	static int[][] tham;
	static int[] d1 = {-1,-1,0,0,1,-1,1,1};
	static int[] d2 = {-1,0,-1,1,0,1,-1,1};
	static int dem;
	
	public static void main(String args[]) throws Exception{
		//System.setIn(new FileInputStream("src/Bao_ve_nong_trang/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		int Answer;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			n = sc.nextInt();
			m = sc.nextInt();
			a = new int[n][m];
			visit = new int[n][m];
			tham = new int[n][m];
			for(int i = 0; i < n; i++){
				for(int j = 0; j < m; j++){
					a[i][j] = sc.nextInt();
				}
			}
			
			dem = 0;
			for(int i = 0; i < n; i++){
				for(int j = 0; j < m; j++){
					if(visit[i][j] == 0){
						bfs(i,j);
					}
				}
			}
			System.out.println("#" + test_case + " " + dem);
		}
	}
	
	public static void bfs(int u, int v){
		int temp = 1;
		int[] q = new int[700*700+5];
		int[] w = new int[700*700+5];
		
		int l = 0, r = 0;
		visit[u][v] = 1;
		q[r] = u;
		w[r] = v;
		r++;
		while(l < r){
			int x = q[l];
			int y = w[l];
			l++;
			for(int i = 0; i < 8; i++){
				int xx = x+d1[i];
				int yy = y+d2[i];
				if(xx>=0 && yy >=0 && xx<n && yy<m){
					if(visit[xx][yy] == 0 && a[xx][yy] == a[u][v]){
						visit[xx][yy] = 1;
						q[r] = xx;
						w[r] = yy;
						r++;
					}
					
					if(a[xx][yy] > a[u][v]){
						temp = 0;
					}
				}
			}
		}
		dem += temp;
	}
}
Editor is loading...