Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.7 kB
2
Indexable
Never
#include<iostream>

using namespace std;
int n,m;
int const size =100000;
int queue[size];
int front=-1;
int rear=-1;
int map_lua[100][100];
int map_ho[100][100];
int map[100][100];
int map_kc[100][100];
int visitLua[100][100];
int ans;
int visitbt[100][100];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

bool isEmpty(){
	return front==rear;
}
void push(int x){
	if(rear==size-1) rear=-1;
	rear++;
	queue[rear]=x;
}
int pop(){
	if(front ==size-1) front=-1;
	front++;
	return queue[front];
}
void reset(){
	for(int i=1; i<100;i++){
		for(int j=1; j<100; j++){
			map_lua[i][j]=0;
			map[i][j]=0;
			map_ho[i][j]=0;
			map_kc[i][j]=0;
			visitLua[i][j]=9999;
			visitbt[i][j]=0;
		}

	}

}
void bfs(int x, int y){
	front=rear=-1;
	push(x);
	push(y);
	visitLua[x][y]=1;
	while(!isEmpty()){
		int x1= pop();
		int y1=pop();
		for(int i=0; i<4; i++){
			int x2= x1+dx[i];
			int y2=y1+dy[i];
			if( x2>=1 && x2<=n && y2>=1 && y2<=m ){
				if( visitLua[x2][y2]>(visitLua[x1][y1]+1)  && map_ho[x2][y2]==0){
					visitLua[x2][y2]=visitLua[x1][y1]+1;
					push(x2);
					push(y2);
				}

			}

		}

	}


}
bool done(int x, int y){
	if(map[x][y]==4) return true;
	return false;
}

bool check(int x, int y, int dem){
	if(dem<visitLua[x][y] )  return true;
	return false;
}

void bt(int x, int y, int dem, int diem){
	if(!check(x,y,dem)) return;
	if(done(x,y)){
		if(ans<diem) ans=diem;
		
	}
	for(int i=0; i<4; i++){
		int x1=x+dx[i];
		int y1=y+dy[i];
		if( x1>=1 && x1<=n && y1>=1 && y1<=m && visitbt[x1][y1]==0){
			if(map_ho[x1][y1]==2){
				if(check(x1,y1,dem)){
					visitbt[x1][y1]=1;
					bt(x1,y1,dem+2,diem+map_kc[x1][y1]);
					visitbt[x1][y1]=0;
				}

			}else {
				visitbt[x1][y1]=1;
				bt(x1,y1,dem+1,diem+map_kc[x1][y1]);
				visitbt[x1][y1]=0;
			}


		}

	}

}




int main(){
	//freopen("text.txt","r",stdin);
	int t;
	cin>>t;
	for(int testcase = 1; testcase <= t ; testcase ++){
		int x_hugo, y_hugo;
		cin>>n>>m>>x_hugo>>y_hugo;
		reset();
		int nlua;
		cin>>nlua;
		for(int i=0; i<nlua; i++){
			int a,b;
			cin>>a>>b;
			map_lua[a][b]=1;
		}
		int nho;
		cin>> nho;
		for(int i=0; i<nho;i++){
			int a,b;
			cin>>a>>b;
			map_ho[a][b]=2;
		}
		int nloithoat;
		cin>> nloithoat;
		for(int i=0; i< nloithoat; i++){
			int a,b;
			cin>>a>>b;
			map[a][b]=4;
		}
		map[x_hugo][y_hugo]=3;
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				cin>>map_kc[i][j];
				if(map_lua[i][j]==1){
					bfs(i,j);
				}

			}

		}
		 ans=-1;
		 visitbt[x_hugo][y_hugo]=1;
		bt(x_hugo,y_hugo,1,map_kc[x_hugo][y_hugo]);
		cout<<"Case #"<<testcase<<endl<<ans<<endl;
	}

	return 0;
}