Future Vision

输入的第一行包含一个整数 $t(1 \le t \le 100)$ ，表示接下来有 $t$ 组测试。
每个测试用例的第一行包含两个整数 $n$ 和 $m$ $(1 \le n,m \le 100)$ 。

接下来 $n$ 行每行包含 $m$ 个字符,表示Kyooma所在的迷宫。并且这些迷宫中的字符中的每一个都是以下字符之一：

'#' --- 表示当前格是一堵墙

'.' --- 表示当前格是一个空地

'H' --- 表示Kyooma在迷宫中的初始位置, 而且这是一个空地

题目保证每组测试用例中都有且只有一个 ‘H'。
下一行包含一个整数 $k(1\le k\le n\times m)$ ，即你预测了接下来 $k$ 分钟剑的位置。
之后 $k$ 行每行包含两个整数 $x,y(1 \le x \le n , 1 \le y \le m)$ ，表示从第 $0$ 分钟到第 $k-1$ 分钟剑的位置。

对于每组测试数据单独输出一行。
如果Kyooma可以成功找到他的剑，输出"YES"（不包含引号）和他最快能找到剑的时刻，用空格分隔。否则，输出"NO"（不包含引号）。

C++ 解法, 执行用时: 240ms, 内存消耗: 460K, 提交时间: 2022-05-04 00:48:51

#include<bits/stdc++.h>
using namespace std;
struct node {
	int x,y;
	int step;
};
int dx[]= {-1,0,1,0},dy[]= {0,-1,0,1};
int main() {
	int t;
	cin>>t;
	while(t--) {
		int n,m,a[110][110]= {},sx,sy;
		char s[110][110]={};
		memset(a,0x3f,sizeof(a));
		cin>>n>>m;
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++) {
				cin>>s[i][j];
				if(s[i][j]=='H')sx=i,sy=j;
			}
		queue<node>q;
	
		q.push({sx,sy,0});
		a[sx][sy]=0;
		s[sx][sy]='#';
		while(!q.empty()) {
			node t=q.front();
			a[t.x][t.y]=t.step;
			q.pop();
			for(int i=0; i<4; i++) {
				int nx=t.x+dx[i],ny=t.y+dy[i];
				if(nx>0&&nx<=n&&ny>0&&ny<=m&&s[nx][ny]=='.') {
					q.push({nx,ny,t.step+1});
					s[nx][ny]='#';
				}

			}
		}
		int k,x,y,f=0,fmax=12345678;
		cin>>k;
		int kk=k;
	for(int i=0;i<k;i++){
			cin>>x>>y;
			if(a[x][y]<=i){
			f=1;
			if(fmax>i)fmax=i;
			}
		}
		if(!f)puts("NO");
		else {
			cout<<"YES "<<fmax<<endl;
		}
	}
	return 0;
}

pypy3 解法, 执行用时: 2759ms, 内存消耗: 32436K, 提交时间: 2021-12-18 19:15:41

from queue import*
fx=[[0,1],[0,-1],[-1,0],[1,0]]
for _ in range(int(input())):
    n,m=map(int,input().split())
    a=[0]+list(' '+input() for i in range(n))
  #  print(a)
    for i in range(1,n+1):
        for j in range(1,m+1):
            if a[i][j]=='H':
                y=i
                x=j
                break
    Q=Queue()
    Q.put([y,x,0])
    dp=[[10**20]*(m+1) for i in range(n+1)]
    #dp[y][x]=0
    while Q.qsize():
        y,x,cnt=Q.get()
        if dp[y][x]<=cnt:
            continue
        dp[y][x]=cnt
        for dy,dx in fx:
            Y=y+dy 
            X=x+dx
            if 1<=X<=m and 1<=Y<=n and a[Y][X]=='.':
                Q.put([Y,X,cnt+1])
    F=-1
    for c in range(int(input())):
        y,x=map(int,input().split())
        if dp[y][x]<=c and F==-1:
            F=c
    print('NO' if F==-1 else 'YES '+str(F))

详情