第四题 wolf
kradcigam
2019-06-29 11:32:18
## 第四题 wolf
是我想用来拉开差距的一题。
不会这道题的同学可以直接打"No"，稳稳拿到20分。
很多同学用了贪心
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
cout<<"No";
return 0;
}
```
多好，目标不高，拿的**稳**！
当然赵海鲲的正解标程，可不是这样做的，用了宽搜，听说毕大佬用了深搜，em，玄学。
两步的宽搜吗，`so easy`
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[55][110][110],mp[110][110],sx,sy,ex,ey,o[55][110][110];
deque<int>q1;
deque<int>q2;
deque<int>ti;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int main(){
memset(mp,-1,sizeof(mp));
int b,n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;
cin>>ch;
if(ch!='#')mp[i][j]=0;
if(ch=='y')sx=i,sy=j;
if(ch=='x')ex=i,ey=j;
}
}
cin>>b;
for(int i=1;i<=b;i++){
char ch;
cin>>ch;
switch(ch){
case 'u':sx--;break;
case 'd':sx++;break;
case 'l':sy--;break;
case 'r':sy++;break;
}
a[i][sx][sy]=1;
}
q1.push_back(ex);
q2.push_back(ey);
ti.push_back(0);
while(!ti.empty()){
if(ti.front()>=b){
cout<<"No";
return 0;
}
int x=q1.front(),y=q2.front();
for(int i=0;i<4;i++){
int tx=x+dx[i],ty=y+dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[ti.front()+1][tx][ty]==0&&mp[tx][ty]==0){
for(int j=0;j<4;j++){
int nx=tx+dx[j],ny=ty+dy[j];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[ti.front()+1][nx][ny]==0&&o[ti.front()+1][nx][ny]==0&&mp[tx][ty]==0){
o[ti.front()+1][nx][ny]=1;
q1.push_back(nx);
q2.push_back(ny);
ti.push_back(ti.front()+1);
for(int k=ti.front()+2;k<=b;k++){
if(a[k][nx][ny]==1){
cout<<"Yes "<<ti.front()+1;
return 0;
}
}
}
}
}
}
q1.pop_front();
q2.pop_front();
ti.pop_front();
}cout<<"No";
return 0;
}
```
只要细心，就可以做对了，没有什么技术含量。