Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
3.0 kB
1
Indexable
Never
#include <iostream>

using namespace std;
int T, N, M, SR, SC;
int F, L, E;
int arr[20][20];
bool visited[20][20];
int diamond[20][20];
int tmp[20][20];
bool lake[20][20];
int ans, maxA;
bool Exit[20][20];
int nextTime;

class Queue{
public:
	int front, rear;
	int q[10000];
	Queue();
	void enQueue(int value);
	int deQueue();
	void reset();
	bool is_Empty();
};
Queue::Queue(){
	front = -1;
	rear = -1;
}
void Queue::enQueue(int value){
	q[++rear] = value;
}
int Queue::deQueue(){
	return q[++front];
}

void Queue::reset(){
	front = -1;
	rear = -1;
}
bool Queue::is_Empty(){
	return front == rear;
}

int X[4] = {-1, 1, 0, 0};
int Y[4] = {0, 0, -1, 1};

Queue rQueue, cQueue;

void expand(){
	while(rQueue.is_Empty() == false){
		int cr = rQueue.deQueue();
		int cc = cQueue.deQueue();
		for(int i = 0; i < 4; i++){
			int nr = cr + X[i];
			int nc = cc + Y[i];
			if(nr >= 0 && nr < N && nc >= 0 && nc < M && lake[nr][nc] == 0 && tmp[nr][nc] == 1000000){
				tmp[nr][nc] = tmp[cr][cc] + 1;
				rQueue.enQueue(nr);
				cQueue.enQueue(nc);
			}
		}		
	}
}



void backtrack(int row, int col, int tm){

	if(Exit[row][col]){
		if(ans > maxA){
			maxA = ans;
		}
	}
	for(int i = 0; i < 4; i++){
		int nrow = row + X[i];
		int ncol = col + Y[i];
		if(nrow >= 0 && nrow < N && ncol >= 0 && ncol < M && visited[nrow][ncol] == false){
			if(lake[nrow][ncol] == false){
				nextTime = tm + 1;
				if(nextTime < tmp[nrow][ncol]){
					ans += diamond[nrow][ncol];
					visited[nrow][ncol] = true;
					backtrack(nrow, ncol, nextTime);
					ans -= diamond[nrow][ncol];
					visited[nrow][ncol] = false;
				}
			}else{
				nextTime = tm + 2;
				if(nextTime < tmp[nrow][ncol]){
					ans += diamond[nrow][ncol];
					visited[nrow][ncol] = true;
					backtrack(nrow, ncol, nextTime);
					ans -= diamond[nrow][ncol];
					visited[nrow][ncol] = false;
				}
			}
		}
	}
}
int main(){
	freopen("input.txt", "rt", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> N >> M >> SR >> SC;
		SR--, SC--;
		arr[SR][SC] = 0;
		int x, y;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				tmp[i][j] = 1000000;
				visited[i][j] = false;
				Exit[i][j] = false;
				lake[i][j] = false;
			}
		}

		rQueue.reset();
		cQueue.reset();

		cin >> F;
		for(int i = 0; i < F; i++){
			cin >> x >> y;
			x--; y--;
			rQueue.enQueue(x);
			cQueue.enQueue(y);
			tmp[x][y] = 0;
		}
		cin >> L;
		for(int i = 0; i < L; i++){
			cin >> x >> y;
			x--; y--;
			lake[x][y] = true;
		}
		cin >> E;
		for(int i = 0; i < E; i++){
			cin >> x >> y;
			x--; y--;
			Exit[x][y] = true;
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				cin >> diamond[i][j];
			}
		}
		ans = diamond[SR][SC];
		visited[SR][SC] = true;
		expand();
		maxA = -1;
		backtrack(SR, SC, 0);
		cout << "Case #" << tc << endl;
		cout << maxA << endl;
	}
	return 0;
}
Leave a Comment