题意:有一副二维地图'S'为起点,'D'为终点,'.'是可以行走的,'X'是不能行走的。问能否只走T步从S走到D?

题解:最容易想到的就是DFS暴力搜索,,但是会超时。。。=_=。。。 所以,,要有其他方法适当的剪枝;假设当前所在的位置为(x,y),终点D的位置为(ex,ey); 那么找下规律可以发现: 当 |x-ex|+|y-ey| 为奇数时,那么不管从(x,y)以何种方式走到(ex,ey)都是花费奇数步;当为偶数时同理。  这即是所谓的奇偶性剪枝。这样剪枝就可以复杂度就变为原来暴力DFS的开根号(原来复杂度不清楚该怎么计算...=_=...)

 /**
* @author Wixson
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <map>
#include <set>
const int inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double EPS=1e-;
using namespace std;
typedef long long ll;
typedef pair<int,int> P; int n,m,t;
char str[][];
int ans;
int sx,sy,ex,ey;
int book[][];
int Next[][]={{,},{,},{,-},{-,}};
//
int abs(int x)
{
return x>?x:-x;
}
void dfs(int x,int y,int cnt)
{
if(str[x][y]=='D')
{
if(cnt==t)
{
ans=;
}
return;
}
//
if(cnt==t) return;
//
int temp=abs(x-ex)+abs(y-ey);
if(temp%!=(t-cnt)%) return;
//
//printf("%d %d -- %d\n",x,y,cnt);
for(int k=;k<;k++)
{
int tx=x+Next[k][],ty=y+Next[k][];
//
if(tx<||tx>=n||ty<||ty>=m||book[tx][ty]||str[tx][ty]=='X') continue;
//
book[tx][ty]=;
dfs(tx,ty,cnt+);
book[tx][ty]=;
if(ans) return;
}
}
//
int main()
{
//freopen("input.txt","r",stdin);
while(scanf("%d%d%d",&n,&m,&t)&&(n||m||t))
{
ans=;
for(int i=;i<n;i++) scanf("%s",str[i]);
//
memset(book,,sizeof(book));
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(str[i][j]=='S') sx=i,sy=j;
if(str[i][j]=='D') ex=i,ey=j;
}
}
//
book[sx][sy]=;
dfs(sx,sy,);
//
if(ans) printf("YES\n");
else printf("NO\n");
}
return ;
}
05-11 16:22
查看更多