北京营销型网站建设seo网站推广案例

题目链接：点击打开链接

题目描述：给定一个迷宫，给一个起点和一个终点，问能否恰好经过T步到达终点？每个格子不能重复走

解题思路：dfs+剪枝

剪枝1：奇偶剪枝，判断终点和起点的距离与T的奇偶性是否一致，如果不一致，直接剪掉

剪枝2：如果从当前到终点的至少需要的步数nt加上已经走过的步数ct大于T，即nt+ct>t剪掉

剪枝3：如果迷宫中可以走的格子小于T直接剪掉

启发：剪枝的重要性

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int n,m,t;
char g[10][10];
int sx,sy,dx,dy;
bool flag[10][10];
const int nx[]= {0,1,0,-1};
const int ny[]= {1,0,-1,0};
bool dfs(int x,int y,int ct)
{if(x==dx&&y==dy){if(t==ct)return true;elsereturn false;}if(abs(dx-x)+abs(dy-y)+ct<=t){for(int i=0; i<4; ++i){int ntx=x+nx[i];int nty=y+ny[i];if(ntx<=n&&ntx>=1&&nty<=m&&nty>=1&&g[ntx][nty]=='.'&&!flag[ntx][nty]){flag[ntx][nty]=true;if(dfs(ntx,nty,ct+1)) return true;flag[ntx][nty]=false;}}}return false;
}
int main()
{while(scanf("%d%d%d",&n,&m,&t)==3&&(n!=0||m!=0||t!=0)){int cut=0;for(int i=1; i<=n; ++i){scanf("%s",&g[i][1]);for(int j=1; j<=m; ++j){if(g[i][j]=='S') sx=i,sy=j;if(g[i][j]=='D') dx=i,dy=j;if(g[i][j]=='.') cut++;}}if(abs(dx-sx)+abs(dy-sy)>t||cut<t-1||(abs(dx-sx)+abs(dy-sy))%2!=t%2){printf("NO\n");continue;}memset(flag,false,sizeof(flag));flag[sx][sy]=true;g[dx][dy]='.';if(dfs(sx,sy,0))printf("YES\n");elseprintf("NO\n");}return 0;
}