Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.0 kB
2
Indexable
Never
#include <iostream>
using namespace std;

int N, M;
int x_start, y_start;
int numFires, numLakes, numGates;
int map[20][20];
int fires[20][20];
int diamonds[20][20];
int visited[20][20];
int dx[] = {-1, 0,  0, 1};
int dy[] = { 0, 1, -1, 0};
int fires_index[20][2];

// Queue
int qx[100000];
int qy[100000];
int front;
int rear;
bool isEmpty(){
	return front == -1;
}
void push(int x, int y){
	if(front == -1) front = 0;
	rear++;
	qx[rear] = x;
	qy[rear] = y;
}
void pop(){
	if(front >= rear) front = rear = -1;
	else front++;
}

// Nhap - Xuat
void nhap(){
	cin >> N >> M;
	cin >> x_start >> y_start;
	map[x_start - 1][y_start - 1] = 1;

	cin >> numFires;
	for(int i = 0; i < numFires; i++){
		int x, y;
		cin >> x >> y;
		fires[x - 1][y - 1] = 1;
		fires_index[i][0] = x - 1;
		fires_index[i][1] = y - 1;
	}

	cin >> numLakes;
	for(int i = 0; i < numLakes; i++){
		int x, y;
		cin >> x >> y;
		map[x - 1][y - 1] = 2;
		fires[x - 1][y - 1] = -1;
	}

	cin >> numGates;
	for(int i = 0; i < numGates; i++){
		int x, y;
		cin >> x >> y;
		map[x - 1][y - 1] = 3;
	}

	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cin >> diamonds[i][j];
		}
	}

}
void xuat(){
	// Map
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;

	//// Fires
	//for(int i = 0; i < N; i++){
	//	for(int j = 0; j < M; j++){
	//		cout << fires[i][j] << " ";
	//	}
	//	cout << endl;
	//}
	//cout << endl;

	//// Diamonds
	//for(int i = 0; i < N; i++){
	//	for(int j = 0; j < M; j++){
	//		cout << diamonds[i][j] << " ";
	//	}
	//	cout << endl;
	//}
	//cout << endl;

	// Visited
	//for(int i = 0; i < N; i++){
	//	for(int j = 0; j < M; j++){
	//		cout << visited[i][j] << " ";
	//	}
	//	cout << endl;
	//}
	//cout << endl;
}

// Reset
void reset(){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			visited[i][j] = 1000000;
		}
	}
}

// Check
bool check(int x, int y){
	return x >= 0 && x < N && y >= 0 && y < M;
}

// BFS
void BFS(int x, int y){
	front = rear = -1;
	push(x,y);
	visited[x][y] = 1;

	while(!isEmpty()){
		int topx = qx[front];
		int topy = qy[front];
		pop();

		for(int i = 0; i < 4; i++){
			int x1 = topx + dx[i];
			int y1 = topy + dy[i];

			if(check(x,y) && fires[x1][y1] == 0 && visited[x1][y1] > visited[topx][topy]){
				if(visited[x1][y1] > visited[topx][topy] + 1){
					visited[x1][y1] = visited[topx][topy] + 1;
					push(x1, y1);
				}
			}
		}
	}
}

void Try(int x, int y){
	if(map[x][y] == 3){
		// Do
		return;
	}
}


int main(){
	freopen("input.txt", "r", stdin);
	int T; cin >> T;

	for(int tc = 1; tc <= T; tc++){
		nhap();

		reset();

		// BFS fire
		for(int i = 0; i < numFires; i++){
			BFS(fires_index[i][0], fires_index[i][1]);
		}

		// Backtrack

		xuat();
	}

	return 0;
}