Untitled
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