Untitled

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

using namespace std;
int m,n;
int kc[50][50],visited[50][50];
int kvc[50][50],klt[50][50];
int kvh[50][50];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int fr,er,maxx;
struct Queue{
	int x;
	int y;
};
Queue queue[10000000];
void enQueue(int xx, int yy){	
	queue[fr].x=xx;
	queue[fr].y =yy;
	fr++;
}
Queue deQueue(){
	Queue t = queue[er];
	er++;
	return t;
}
void BFS(){
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(kvc[i][j]==1){
			enQueue(i,j);
			}
		} 
	}
	while(er!=fr){
		Queue vt = deQueue();
		int xc = vt.x;
		int yc = vt.y;
		for(int i=0;i<4;i++){
			int xi = xc + dx[i];
			int yi= yc + dy[i];
			if(xi > 0 && xi <=m && yi>0 && yi<=n && kvh[xi][yi]==1 ){
				if( kvc[xi][yi]==999999){
					enQueue(xi,yi);
					kvc[xi][yi]=kvc[xc][yc]+1;
					
				}
			}
		}
	}

}
void backtrack(int hang, int cot, int count){
	if(klt[hang][cot]==1){
		if(maxx < count)
			maxx = count;
	}
	for(int i=0;i<4;i++){
			int xi = hang + dx[i];
			int yi= cot + dy[i];
			if(xi > 0 && xi <=m && yi>0 && yi<=n && visited[xi][yi]==0 && kvc[xi][yi] > visited[hang][cot] + kvh[xi][yi])                                                                                      {
				visited[xi][yi] = visited[hang][cot] + kvh[xi][yi];
				backtrack(xi, yi, count + kc[xi][yi]);
				visited[xi][yi]=0;
				
			}
	}
}
int main(int argc, char** argv)
{
	int test_case;
	int T;
	ios::sync_with_stdio(false);
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		fr=er=0;
		int xhugo,yhugo;
		cin >> m >> n >> xhugo >> yhugo;
		int sdc,xdc,ydc;
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++){
				kvc[i][j]=999999;
				visited[i][j]=0;
				klt[i][j]=0;
				kvh[i][j]=1;
				kc[i][j]=0;
			} 
		}
		cin >> sdc;
		for(int i=1;i<=sdc;i++){
			cin >> xdc >> ydc;
			kvc[xdc][ydc]=1; // damchay=1
		}
		int ho,xho,yho;
		cin >> ho;
		for(int i=1;i<=ho;i++){
			cin >> xho >> yho;
			kvh[xho][yho]=2; // ho=3
		}
		int loithoat, xlt, ylt;
		cin >> loithoat;
		for(int i=1;i<=loithoat;i++){
			cin >> xlt >> ylt;
			klt[xlt][ylt]=1; // loithoat=1
		}	
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++){
				cin >> kc[i][j];	
			}
	}
		BFS();
		maxx = -1;
		visited[xhugo][yhugo]=1;
		backtrack(xhugo,yhugo,kc[xhugo][yhugo]);
	
		cout << "Case #" << test_case << endl;
		cout << maxx << endl;
		
	}
	return 0;//Your program should return 0 on normal termination.
}