Question

c++问题，求解

题目描述

森林里有一头狼，它在树林了觅食。突然，它发现了一头羚羊，羚羊也发现了它，转身便跑。狼很有经验，它没有茫然地去追这头鹿，因为，它知道，鹿会在没有动物抓它是在x单位的时间内怎么走，而林子里的路纵横交错，许多地方都有路障，我们可以把林子变成一个n*m的矩形，有n行,m列。狼的位置用字符'x'来表示，羚羊的位置用字符'y'来表示，通路用字符'.'来表示，路障用字符'#'来表示。狼每一单位时间，必须走2格，每一单位时间都不可以与羚羊在同一格，不然就要被羚羊发现了。狼要在羚羊之前来到某地，停止奔跑，进行等待。狼想要知道抓住羚羊的最快的路该怎么走，但它不会算，可是它有一台高科技的笔记本电脑，里面有c++，但是它不会编，于是就请聪明的你，打开c++，编写这个程序吧！

输入输出格式

输入格式：
第1行两个数n m 接下来n行，每行m个字符，表示此格的情况。 接下来1行一个数x 接下来x行，每行1个字符，表示鹿移动的方向，向左是'l'，向右是'r'，向上是'u'向下是'd'

输出格式：
如果可以输出"Good"，引号不用输出，然后，再输出它要跑的最短的单位时间，以便他做好心理准备。一个字符串和一个整数直接用空格隔开。 如果不可以输出"No"，引号不用输出，使它不要在浪费体力。

输入输出样例

输入样例#1： 复制
3 5
. . . . .
# . x y .
# # # # #
2
u
d
输出样例#1： 复制
No
说明

m<=n<=100 x<=50

狼每一单位时间，必须走两格，并且不能在同一时间与羚羊在同一地点。

Answer 1

#include <bits/stdc++.h>
using namespace std;
const int N=105;
char mp[N][N];
bool smp[N][N];
int movex[]={0,0,1,1,-1,-1,2,-2};
int movey[]={2,-2,-1,1,1,-1,0,0};
int n,m;
bool ans=0;
int flag;
int movesx(int sx)
{
if(flag==3||flag==4)
{
return sx;
}

if(flag==1)
{
return sx-1;
}
return sx+1;
}
int movesy(int sy)
{
if(flag==1||flag==2)
{
return sy;
}
if(flag==3)
{
return sy-1;
}
return sy+1;
}
void dfs(int wx,int wy,int sx,int sy)
{
if(wx<=0||wy<=0||wx>n||wy>m||sx<=0||sy<=0||sx>n||sy>m)
{
return;
}
if(smp[wx][wy]==1&&(wx!=sx||wy!=sy))
{
ans=1;
return;
}
for(int i=0;i<8;i++)
{
int nex_wx=wx+movex[i];
int nex_wy=wy+movey[i];
int nex_sx=movesx(sx);
int nex_sy=movesy(sy);
if(mp[nex_wx][nex_wy]=='.'&&mp[nex_sx][nex_sy]=='.')
{
dfs(nex_wx,nex_wy,nex_sx,nex_sy);
}
}
}
int main()
{
cin>>n>>m;
int beg_wx,beg_wy,beg_sx,beg_sy;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='x')
{
beg_wx=i;
beg_wy=j;
}
if(mp[i][j]=='y')
{
beg_sx=i;
beg_sy=j;
}
}
}

int T;
cin>>T;
while(T--)
{
ans=0;
memset(smp,0,sizeof(smp));
char ch;
cin>>ch;
if(ch=='u')
{
flag=1;
for(int i=beg_sx;i>=1;i--)
{
if(mp[i][beg_sy]!='#')
{
smp[i][beg_sy]=1;
}
}
}
if(ch=='d')
{
flag=2;
for(int i=beg_sx;i<=n;i++)
{
if(mp[i][beg_sy]!='#')
{
smp[i][beg_sy]=1;
}
}
}
if(ch=='l')
{
flag=3;
for(int i=beg_sy;i>=1;i--)
{
if(mp[beg_sx][i]!='#')
{
smp[beg_sx][i]=1;
}
}
}
if(ch=='r')
{
flag=4;
for(int i=beg_sy;i<=n;i++)
{
if(mp[beg_sx][i]!='#')
{
smp[beg_sx][i]=1;
}
}
}
dfs(beg_wx,beg_wy,beg_sx,beg_sy);
if(ans)
{
cout<<"Good"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
}
最好给个提交地址，怕错