Untitled

 avatar
unknown
plain_text
10 months ago
1.6 kB
5
Indexable
package protectfam;

import java.io.FileInputStream;
import java.util.*;

public class Solution {
	static final int N = 705;
	static int n, m;
	static int[][] a = new int[N][N], dd = new int[N][N];
	static int ans = 0;
	static int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 };

	static class Pair {
		int first, second;

		Pair(int first, int second) {
			this.first = first;
			this.second = second;
		}
	}

	public static void bfs(int i, int j) {
		int ok = 1;
		Queue<Pair> st = new LinkedList<>();
		st.add(new Pair(i, j));
		dd[i][j] = 1;
		while (!st.isEmpty()) {
			Pair p = st.poll();
			i = p.first;
			j = p.second;
			for (int k = 0; k <= 7; k++) {
				int u = i + dx[k], v = j + dy[k];
				if (u < 1 || u > n || v < 1 || v > m)
					continue;
				if (a[u][v] == a[i][j] && dd[u][v] == 0) {
					dd[u][v] = 1;
					st.add(new Pair(u, v));
				}
				if (a[u][v] > a[i][j])
					ok = 0;
			}
		}
		ans += ok;
	}

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/protectfam/input.txt"));
		Scanner sc = new Scanner(System.in);

		int tc = sc.nextInt();
		for (int t = 1; t <= tc; t++) {
			n = sc.nextInt();
			m = sc.nextInt();
			ans = 0;

			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= m; j++) {
					a[i][j] = sc.nextInt();
					dd[i][j] = 0;
				}
			}

			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= m; j++) {
					if (dd[i][j] == 0)
						bfs(i, j);
				}
			}

			System.out.println(ans);
		}

		sc.close();
	}
}
Editor is loading...
Leave a Comment