Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
2.5 kB
2
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
//class pos{
//	int x;
//	int y;
//	public pos(int x1, int y1) {
//		this.x = x1; 
//		this.y = y1;
//	}
//}
//
//class Queue{
//	static pos[] Data = new pos[10000000];
//	static int front, rear;
//	public Queue() {
//		this.front = this.rear = -1;
//	}
//
//	void reset() {
//		front = rear = -1;
//	}
//
//	public void enQueue(pos value) {
//		Data[++rear] = value;
//	}
//
//	pos deQueue() {
//		return Data[++front];
//	}
//
//	boolean isEmpty() {
//		if (this.front == this.rear) {
//			return true;
//		}
//		return false;
//	}
//}

public class Baovenongtrang {
	static int[][] Map, visited;
	static int n,m, newr, newc, kq;
	static Queue queue;
	static int[] spinr = {0, 0, -1, -1, -1, 1, 1, 1 };
	static int[] spinc = {-1, 1, -1, 0, 1, -1, 0, 1};
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("Text"));
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		for (int Case = 1; Case <= tc; Case++){
			n = sc.nextInt();
			m = sc.nextInt();
			Map = new int[n][m];
			visited = new int[n][m];
			for(int i = 0; i < n; i++){
				for(int j = 0; j < m; j++){
					Map[i][j] = sc.nextInt();
				}
			}
			
			kq = 0;
			pos f;
			for(int k = 0; k < n; k++){
				for(int j = 0; j < m; j++){
					if(visited[k][j] == 0){
						kq++;
						queue = new Queue();
						queue.enQueue(new pos(0,0));
						visited[k][j] = 1;
						while(!queue.isEmpty()){
							f = queue.deQueue();
							for (int i = 0; i < 8; i++){
								newr = f.x + spinr[i];
								newc = f.y + spinc[i];
								if(newr >= 0 && newc >= 0 && newr < n && newc < m
										&& newr <= f.x && newc <= f.y && visited[newr][newc] == 0){
									queue.enQueue(new pos(newr, newc));
									visited[newr][newc] = 1;
								}
							}
						}
					}
					
				}
			}
			System.out.println(kq);
			
		}
	}
}



3

8 7

4 3 2 2 1 0 1

3 3 3 2 1 0 1

2 2 2 2 1 0 0

2 1 1 1 1 0 0

1 1 0 0 0 1 0

0 0 0 1 1 1 0

0 1 2 2 1 1 0

0 1 1 1 2 1 0

8 7

4 3 2 2 1 1 1

3 3 3 2 1 0 1

2 2 2 2 1 0 0

2 1 1 1 1 0 0

1 1 0 0 0 1 0

0 0 0 1 1 1 0

0 1 2 2 1 1 0

0 1 1 1 2 1 0

8 7

4 3 2 2 1 1 1

3 3 3 2 1 0 1

2 2 2 2 1 0 0

2 1 1 2 1 0 0

1 1 2 2 0 1 0

0 0 0 2 1 1 0

0 1 2 2 1 1 0

0 1 1 1 2 1 0

#1 3

#2 2

#3 1