Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
2.5 kB
1
Indexable
Never
#include<iostream>

using namespace std;
int n, m, sr, sc;
int kvkc[20][20];
int kvh[20][20];
int kvc[20][20];
int lt[20][20];
int timee[20][20];
int vthgx, vthgy;
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};
int front, rear;
int visit[20][20];
int ltcx = 0, ltcy = 0;
int maxx = -1;

void init() {
	front = 0;
	rear = 0;
}

struct toado
{
	int x, y;
};

toado queu[500];

void push(int xx, int yy) {
	queu[rear].x = xx;
	queu[rear].y = yy;
	rear++;
}

toado pop() {
	toado t = queu[front];
	front ++;
	return t;
}

void BFSC() {
	init();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <=m; j++) {
			if (kvc[i][j] == 1) {
				push(i, j);
			}
		}
	}
	
	int xn, yn;
	//kvc[x][y] = 1;
	while (front < rear) {
		toado vitri = pop();
		for (int i = 0; i < 4; i++) {
			xn = vitri.x + dx[i];
			yn = vitri.y + dy[i];
			if (xn>0 && xn <= n && yn > 0 && yn <= m && kvh[xn][yn] == 1) {
				if (kvc[xn][yn] == 999999) {
					push(xn, yn);
					kvc[xn][yn] = kvc[vitri.x][vitri.y] + 1;
				}
			}
		}

	}
}


void backtrack(int h, int c, int count) {
	if (lt[h][c] == 1) {
		if (maxx < count) {
			maxx = count;
		}
	}

	for (int i = 0; i < 4; i++) {
		int xn = h + dx[i];
		int yn = c + dy[i];
		if (xn>0 && xn <= n && yn > 0 && yn <= m && visit[xn][yn] == 0 && kvc[xn][yn] > visit[h][c] + kvh[xn][yn]) {
			visit[xn][yn] = visit[h][c] + kvh[xn][yn];
			backtrack(xn, yn, count + kvkc[xn][yn]);
					
			visit[xn][yn] = 0;
		}
	}
}

int main() { 
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r",stdin);
	int sl;
	cin >> sl;
	for (int stt = 1; stt <= sl; stt++) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				kvc[i][j] = 999999;
				kvh[i][j] = 1;
				kvkc[i][j] = 0;
				visit[i][j] = 0;
				lt[i][j] = 0;

			}
		}
		cin >> vthgx >> vthgy;
		int slc, slh, xx, yy, slt;
		cin >> slc;
		for (int i = 1; i <= slc; i++) {
			cin >> xx >> yy;
			kvc[xx][yy] = 1;
		}
		cin >> slh;
		for (int i = 1; i <= slh; i++) {
			cin >> xx >> yy;
			kvh[xx][yy] = 2;
		}
		cin >> slt;
		for (int i = 1; i <= slt; i++) {
			cin >> xx >> yy;
			lt[xx][yy] = 1;
			ltcx = xx;
			ltcy = yy;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> kvkc[i][j];
			}
		}
        BFSC();


		maxx = -1;
		visit[vthgx][vthgy] = 1;
		backtrack(vthgx, vthgy, kvkc[vthgx][vthgy]);
		cout << "Case #"<<stt<<endl;
		cout << maxx <<endl;
	}
	return 0;
}