2022 Hangzhou Electric Multi school first Dragon Slayer (dfs+ state compression)

A long time ago , The Dragon captured the princess . To save the princess , The hero entered the den of the Dragon . The dragon's nest is a rectangular area n Width and width m. The lower left corner is （0,0） In the upper right corner is （n,m）. The position of the hero is (xs+0.5,ys+0.5). The position of the dragon is (xt+0.5,yt+0.5). The area has some horizontal or vertical walls . Heroes can move in any direction within the area , But you can't go through the wall , Including the end of the wall . The hero wants to go where the dragon is , But it may be blocked by the wall . Fortunately, , Heroes can gain special abilities , Every time you use a special ability, you can make a wall disappear forever . Since using special abilities requires a lot of physical strength , So the hero wants to know , At least on the premise of reaching the position of the evil dragon , How many times do you need to use special abilities ？ 

Input

The first line contains integers T(T≤10)- The number of test cases . The first line of each test case contains 3 It's an integer n,m,K(1≤, nanometer ,K≤15)- Length and width of rectangular area , Number of walls The second line of each test case contains 4 It's an integer xs,ys,xt,yt(0≤xs,xt<n,0≤ys,yt<m)— The position of heroes and Dragons . next K That's ok , Each row contains 4 It's an integer x1,y1,x2,y2(0≤x1,x2≤n,0≤y1,y2≤ rice )— Indicates the location of the two endpoints of the wall , Make sure x1=x2 or y1=y2. 

Output

For each test case , One line of output contains an integer , This integer represents at least the number of times a special ability is required . 

Sample input

2

3 2 2

0 0 2 1

0 1 3 1

1 0 1 2

3 2 2

0 0 2 1

2 1 2 2

1 0 1 1 

Sample output

2 0

Ideas ：

Enumerate the state of each wall （ Exist or not exist ）, In binary numbers , Presence marked as 0 Does not exist marked 1, share pow（2,15） States , Make a deep search for the map of each state （ Be careful , Because of the particularity of the wall , The wall needs to be divided into horizontal wall and vertical wall for storage respectively ） Then search deeply for each state （ I really don't understand how such a complicated idea can be called explosive search ）, also , Remember to prune （ans<find(i) continue);

Description of the wall ：

The wall is put into the array when building the drawing , But pay attention to , The wall actually exists only on one side of the array element , That is to say, when the character walks to the left, he will encounter the vertical wall in this case , When you walk to the right, you will encounter the vertical wall of the next grid , When walking down, you will encounter the horizontal wall of this grid , When you walk up, you will encounter the horizontal wall of the next grid . Use this property to judge the end point of deep search .

Code ：

#include <iostream>
#include <cstring>
#include <algorithm>
#define f first
#define s second
using namespace std;
typedef long long LL;
typedef pair<double,double> PDD;
const int N=50,M=1<<15;
int n,m,k;
int f[M];
int pd[N][N],zq[N][N],hq[N][N];// Judge whether you have passed , Longitudinal wall , Cross wall ; 
struct node{
	int x[2],y[2];
}dui[N];
int x1,x2,ys,y2;

void init(){
	memset(pd,0,sizeof pd);
	memset(zq,0,sizeof zq);
	memset(hq,0,sizeof hq);
}

int find(int x){// Find the number of removed walls corresponding to each state  
	int cs=0;
	for(int i=0;i<k;i++){
		cs+=x>>i&1;
	}
	return cs;
}

int dfs(int x,int y){
	if(x==x2&&y==y2) return 1;
	int res=0;
	if(x-1>=0&&pd[x-1][y]==0&&zq[x][y]==0){
		pd[x-1][y]=1;
		res=max(dfs(x-1,y),res);
		pd[x-1][y]=0;
	}
	if(x+1<n&&pd[x+1][y]==0&&zq[x+1][y]==0){
		pd[x+1][y]=1;
		res=max(dfs(x+1,y),res);
		pd[x+1][y]=0;	
	}
	if(y-1>=0&&pd[x][y-1]==0&&hq[x][y]==0){
		pd[x][y-1]=1;
		res=max(dfs(x,y-1),res);
		pd[x][y-1]=0;
	}
	if(y+1<m&&pd[x][y+1]==0&&hq[x][y+1]==0){
		pd[x][y+1]=1;
		res=max(res,dfs(x,y+1));
		pd[x][y+1]=1;
	}
	return res;
}

bool check(int s){
	init();// Initialize array  
	for(int i=0;i<k;i++){// Drawing  
		if(((s>>i)&1)==0){
			if(dui[i].x[0]==dui[i].x[1]){
				for(int j=dui[i].y[0];j<dui[i].y[1];j++){
					zq[dui[i].x[0]][j]++;
				}
			}
			else{
				for(int j=dui[i].x[0];j<dui[i].x[1];j++){
					hq[j][dui[i].y[0]]++;
				}
			}
		}
	}
	pd[x1][ys]=1;
	return dfs(x1,ys);//dfs Judge whether this state can reach the end  
}

int main(){
	int t;
	cin>>t;
	while(t--){
		int ans=20;
		cin>>n>>m>>k;
		memset(f,0,sizeof f);
		cin>>x1>>ys>>x2>>y2;
		for(int i=0;i<k;i++){
			cin>>dui[i].x[0]>>dui[i].y[0]>>dui[i].x[1]>>dui[i].y[1];
			if(dui[i].x[0]>dui[i].x[1]) swap(dui[i].x[0],dui[i].x[1]);
			if(dui[i].y[0]>dui[i].y[1]) swap(dui[i].y[0],dui[i].y[1]);		
		}
		for(int i=0;i<1<<k;i++){// Traversal state  
			if(f[i]==0&&find(i)<ans){// prune  
				f[i]=check(i);
				if(f[i]){
					ans=min(ans,find(i));
				} 
			}
		}
		cout<<ans<<endl;	
	}
	
	return 0;
}