当前位置:网站首页>Search: Future Vision (moving sword)
Search: Future Vision (moving sword)
2022-07-05 22:03:00 【zheng. ys】
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;
}
边栏推荐
- 华为云ModelArts文本分类–外卖评论
- 如何开发引入小程序插件
- 深信服X计划-网络协议基础 DNS
- Huawei fast game failed to call the login interface, and returned error code -1
- Comment développer un plug - in d'applet
- Blocking protocol for concurrency control
- Pointer parameter passing vs reference parameter passing vs value parameter passing
- Overview of concurrency control
- The real situation of programmers
- The simple problem of leetcode is to split a string into several groups of length K
猜你喜欢
MATLAB | App Designer·我用MATLAB制作了一款LATEX公式实时编辑器
Database recovery strategy
数博会精彩回顾 | 彰显科研实力,中创算力荣获数字化影响力企业奖
ICMP 介绍
Create a virtual machine on VMware (system not installed)
多家呼吸机巨头产品近期被一级召回 呼吸机市场仍在增量竞争
Defect detection - Halcon surface scratch detection
Stored procedures and stored functions
ICMP introduction
Huawei game multimedia service calls the method of shielding the voice of the specified player, and the error code 3010 is returned
随机推荐
Blocking of concurrency control
Poj3414 extensive search
Pointer parameter passing vs reference parameter passing vs value parameter passing
Getting started with microservices (resttemplate, Eureka, Nacos, feign, gateway)
Huawei fast game failed to call the login interface, and returned error code -1
Oracle checkpoint queue - Analysis of the principle of instance crash recovery
让开发效率提升的跨端方案
Implementing Lmax disruptor queue from scratch (IV) principle analysis of multithreaded producer multiproducersequencer
Matlab | app designer · I used Matlab to make a real-time editor of latex formula
C language knowledge points link
boundary IoU 的计算方式
Analyse des risques liés aux liaisons de microservices
How to use tensorflow2 for cat and dog classification and recognition
Learning of mall permission module
Oracle views the data size of a table
Server optimization of performance tuning methodology
An exception occurred in Huawei game multimedia calling the room switching method internal system error Reason:90000017
EBS Oracle 11g cloning steps (single node)
Create a virtual machine on VMware (system not installed)
阿龙的感悟