Search: Future Vision (moving sword)

Topic link ：https://codeforces.com/gym/103488/problem/F?mobile=true

Kyooma There is a sword , He likes to use this sword to fencing with others . one day , His sword suddenly passed away , therefore Kyooma Start looking for his sword .

After a long journey ,Kyooma Finally came to the door of a maze . He knew that his sword must be somewhere in the maze , But his sword can blink in this maze ！

Now? ,Kyooma Ask you for help . Please tell him if he can find the sword , Because you can use your special abilities   Futuristic vision   Predict in the next kk Where will the sword be in minutes .

The maze is made up of n That's ok m The square of the column consists of ,Kyooma Every minute can go up 、 Next 、 Left 、 Move right to the adjacent square , Or do nothing .Kyooma In the 0 Minutes are at the starting position .

Kyooma Don't go through the wall or climb up the wall ,  But he can reach where the sword appears and wait for it .

Notice that the sword can appear above the wall , And the sword will be in the k−1 After minutes, the permanent transmission leaves the maze , It means Kyooma Will never find his sword ！

Input

The first line of input contains an integer  t(1≤t≤100), It means that there is tt Group test .

The first line of each test case contains two integers  n  and  m (1≤n,m≤100).

Next  n  Each line contains m Characters , Express Kyooma Maze where . And each of these characters in the maze is one of the following characters ：

• '#' — Indicates that the current grid is a wall
• '.' — Indicates that the current grid is an empty space
• 'H' — Express Kyooma The initial position in the maze , And this is an open space

The title ensures that there is only one test case in each group 'H'.

The next line contains an integer k(1≤k≤n×m), That is, you predicted the next kk The position of the minute sword .

after k Each line contains two integers x,y(1≤x≤n,1≤y≤m), Says from the first 0 Minutes to k−1 The position of the minute sword .

Output

For each group of test data, output a separate line .

If Kyooma Can successfully find his sword , Output "YES"（ No quotation marks ） and The moment when he can find the sword as soon as possible , Separate... With spaces . otherwise , Output "NO"（ No quotation marks ）.

Their thinking ： First find out the time to each position , Then compare , If you reach a certain position before the sword , Then this position may be the answer , Then find the answer that takes the least time .

#include<iostream>
#include<queue>
using namespace std;

typedef long long ll;

int nex[4][2]={1,0,-1,0,0,1,0,-1};
int sx,sy;

struct node
{
	int x,y,step;
};

void solve()
{
	int n,m;
	cin>>n>>m;
	
	char str[200][200];
	for(int i=0;i<n;i++)
		cin>>str[i];
	
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(str[i][j]=='H')
				sx=i,sy=j;
	
	int a[200][200];
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
			a[i][j]=-1;
	
	queue<node>zheng;
	node r;
	r.step=0,r.x=sx,r.y=sy;
	zheng.push(r);
	a[sx][sy]=0;
	
	while(!zheng.empty())
	{
		node t=zheng.front();
		zheng.pop();
		
		int x=t.x,y=t.y,step=t.step;
		
		for(int i=0;i<4;i++)
		{
			int nx=x+nex[i][0];
			int ny=y+nex[i][1];
			if(nx<0||ny<0||nx>=n||ny>=m)
				continue;
			if(str[nx][ny]=='#'||a[nx][ny]!=-1)
				continue;
			r.step=step+1,r.x=nx,r.y=ny;
			zheng.push(r);
			a[nx][ny]=r.step;
		}
	}
	
	int k,ans=2e9;
	cin>>k;
	
	for(int i=0;i<k;i++)
	{
		int x,y;
		cin>>x>>y;
		if(ans!=2e9)continue;
		if(a[x-1][y-1]!=-1&&a[x-1][y-1]<=i)
			ans=i;
	}
	
	if(ans==2e9)
		cout<<"NO"<<endl;
	else
		cout<<"YES "<<ans<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--) 
		solve();
	
	return 0;
}