Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.8 kB
0
Indexable
Never
#include <iostream>
using namespace std;

int a[701][701], n, m;
bool vt[701][701];
int rspin[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int cspin[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const int MAX_SIZE = 100000;

struct Point {
	int x, y;
};

template <typename T>
class Queue {
private:
	T data[MAX_SIZE];
	int front, rear;
public:
	Queue() {
		front = -1;
		rear = -1;
	}
	bool isFull() {
		return rear == MAX_SIZE - 1;
	}
	bool isEmpty() {
		return front == rear;
	}
	void enQueue(T val) {
		if (!isFull())
			data[++rear] = val;
	}
	T deQueue() {
		if (!isEmpty())
			return data[++front];
	}
	void reset() {
		front = -1;
		rear = -1;
	}
	T peek() {
		return data[front+1];
	}
};

Queue<Point> q;

int main() {
	//freopen("input.txt", "r", stdin);
	int t;
	cin>>t;
	for(int tc = 1; tc <= t; tc++) {
		int result = 0;
		cin>>n>>m;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				cin>>a[i][j];
				vt[i][j] = false;
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if (!vt[i][j]) {
					bool flag = true;
					q.reset();
					Point temp = {i, j};
					q.enQueue(temp);
					vt[i][j] = true;
					while(!q.isEmpty()) {
						Point cur = q.deQueue();
						for(int k = 0; k < 8; k++) {
							int x = cur.x + rspin[k];
							int y = cur.y + cspin[k];
							if (x >= 0 && y >= 0 && x < n && y < m) {
								if (!vt[x][y]) {
									if (a[x][y] == a[cur.x][cur.y]) {
										Point tmp = {x, y};
										q.enQueue(tmp);
										vt[x][y] = true;
									}
								}
								if (a[x][y] > a[cur.x][cur.y]) {
									flag = false;
								}
							}
						}
					}
					
					if (flag) {
						result++;
					}

				}
			}
		}
		cout<<"#"<<tc<<" "<<result<<endl;
	}
	return 0;
}
Leave a Comment