题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1010
题目大意：
输入 n m t,生成 n*m 矩阵,矩阵元素由 ‘.’ 'S' 'D' 'X' 四类元素组成.
S'代表是开始位置； 'D'表示结束位置；'.'表示可以走的路；'X'表示是墙。
问:从‘S’ 能否在第 t 步 正好走到 'D'.
解题思路：
平常心态做dfs即可，稍微加个奇偶剪枝，第一次做没经验，做过一次下次就知道怎么做了。最后有代码注释解析。
AC Code:
#include<bits/stdc++.h>
using namespace std;
int n,m,t;
int doorX,doorY;
char ca[][];
int to[][] = {{,-},{,},{-,},{,}};
int dfs(int x,int y,int cnt)
{
if(x>n||y>m||x<=||y<=)return ;
if(cnt==t&&x==doorX&&y==doorY)
return ;
int tem=t-cnt-abs(x-doorX)-abs(y-doorY);
if(tem< || tem& )return ;
for(int i=; i<; i++)
{
if(ca[x+to[i][]][y+to[i][]]!='X')
{
ca[x+to[i][]][y+to[i][]]='X';
if(dfs(x+to[i][],y+to[i][],cnt+))return ;
ca[x+to[i][]][y+to[i][]]='.';
}
}
return ;
}
int main()
{
while(scanf("%d%d%d",&n,&m,&t)!=EOF&&n+m+t)
{
int i,j,wall=,stratX,stratY;
getchar();
for(i=; i<=n; i++)
{
for(j=; j<=m; j++)
{
scanf("%c",&ca[i][j]);
if(ca[i][j]=='S')
stratX=i,stratY=j;
else if(ca[i][j]=='X')
wall++;
else if(ca[i][j]=='D')
doorX=i,doorY=j;
}
getchar();
}
if(n*m-wall<=t)
{
printf("NO\n");
continue;
}
ca[stratX][stratY]='X';
if(dfs(stratX,stratY,))
printf("YES\n");
else
printf("NO\n");
}
return ;
}
代码解析：
#include<bits/stdc++.h>
using namespace std;
int n,m,t;//n*m 矩阵 和 走的步数 t
int doorX,doorY;//门的位置
char ca[][];//矩阵大小
int to[][] = {{,-},{,},{-,},{,}};
int dfs(int x,int y,int cnt)
{
if(x>n||y>m||x<=||y<=)return ;//位置越界
if(cnt==t&&x==doorX&&y==doorY)//已走步数 == 要走的步数 t，且位置刚好是门的位置，成功找到一条路
return ;
//！ { 奇偶性剪枝：
int tem=t-cnt-abs(x-doorX)-abs(y-doorY);
if(tem< || tem& )return ;
// 剩余的步数小于0 || tem 为奇数 都不满足 return 0 即可！} //@{ 遍历八个方向 递归dfs 如果有条件满足 return 1,否则结束 return 0;
for(int i=; i<; i++)
{
if(ca[x+to[i][]][y+to[i][]]!='X')
{
ca[x+to[i][]][y+to[i][]]='X';
if(dfs(x+to[i][],y+to[i][],cnt+))return ;
ca[x+to[i][]][y+to[i][]]='.';
}
}
return ;
// @}
}
int main()
{
while(scanf("%d%d%d",&n,&m,&t)!=EOF&&n+m+t)
{
int i,j,wall=,stratX,stratY;
getchar();
// 001 { 记录开始位置，墙的个数，以及门的位置
for(i=; i<=n; i++)
{
for(j=; j<=m; j++)
{
scanf("%c",&ca[i][j]);
if(ca[i][j]=='S')
stratX=i,stratY=j;
else if(ca[i][j]=='X')
wall++;
else if(ca[i][j]=='D')
doorX=i,doorY=j;
}
getchar();
}
// 001 }
//002 {剪一下枝： 如果墙的个数+走的步数>=矩阵单元的个数，则肯定无法完成此任务，因为还要有开始和门的位置存在
if(n*m-wall<=t)
{
printf("NO\n");
continue;
}
//002 }
ca[stratX][stratY]='X';//003 { 将开始位置置为墙不可再次访问 } if(dfs(stratX,stratY,))
printf("YES\n");
else
printf("NO\n");
}
return ;
}