Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.5 kB
1
Indexable
Never
#include<iostream>

using namespace std;

int mover[8]={-1,-1,0,1,1,1,0,-1};
int movec[8]={0,1,1,1,0,-1,-1,-1};

int mang[100][100];
int check[100][100];
int t,m,n,ans;

class queue{
	int front;
	int rear;
	int mang[1000];
public:
	queue(){
		front=-1;
		rear=-1;
	}
	void push(int x){
		rear++;
		mang[rear]=x;
	}
	void pop(){
		front++;
	}
	int peak(){
		return mang[front+1];
	}
	int isempty(){
		if(front==rear) return 1;
		return 0;
	}
	int isfull(){
		if(rear==999) return 1;
		return 0;
	}
	void reset(){
		front=-1;
		rear=-1;
	}
};

void bfs(int x, int y){
	queue queue1;
	queue queue2;
	queue1.push(x);
	queue2.push(y);
	check[x][y]=1;
	while(queue1.isempty()==0){
		int r=queue1.peak(); int c=queue2.peak();
		queue1.pop();
		queue2.pop();
		for(int h=0;h<8;h++){
			int a=r; int b=c;
			a+=mover[h]; b+=movec[h];
			if(check[a][b]==0 && a>=0 && a<m && b>=0 && b<n && mang[a][b]==1){
				queue1.push(a);
				queue2.push(b);
				check[a][b]=1;
			}
		}
	}
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> t;
	for(int tc=1;tc<=t;tc++){
		cin >> m >> n;
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				cin >> mang[i][j];
				check[i][j]=0;
			}
		}
		ans=0;
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				if(check[i][j]==0 && mang[i][j]==1){
					ans++;
					bfs(i,j);
				}
			}
		}
		cout << "#" << tc <<  " " << ans << endl;
	}


	return 0;
}
Leave a Comment