学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1010

#include <iostream>
#include <cmath>
using namespace std;

char M[8][8];
int dir[4][2] = {{0, -1},{0, 1},{-1, 0},{1, 0}};
int di, dj;//终点
int n, m, time, wall;
bool isfind;
void search(int x, int y, int _t)
{
 int i;
 if (x < 0 || y < 0 || x > n || y > m)
  return ;
 if (x == di && y == dj && _t == time) {
  isfind = true;
  return ;
 }
 if ( (abs(x-di)+abs(y-dj))%2 != (time-_t)%2 ) { 
  return ;
 }
 for (i = 0; i < 4; i++) {
  if (M[ x+dir[i][0] ][ y+dir[i][1] ] != 'X') {
   M[ x+dir[i][0] ][ y+dir[i][1] ] = 'X';
   search(x+dir[i][0], y+dir[i][1], _t+1); //从当前位置继续走下一步
   if (isfind) return ;//返回的找到出口时，返回函数
   M[ x+dir[i][0] ][ y+dir[i][1] ] = '.';//否则，回朔要恢复之前
  }
 }
 return ;
}
int main()
{
 int i, j;
 int si, sj;
 while (scanf("%d %d %d", &n, &m, &time) && (n+m+time)) {
  wall = 0;
  isfind = false;
  getchar();
  for (i = 0; i < n; i++) { //初始化迷宫
   for (j = 0; j < m; j++) {
    scanf("%c",&M[i][j]);
    if (M[i][j] == 'S') {si = i; sj = j;}//起点
    else if (M[i][j] == 'D') {di = i; dj = j;}
    else if (M[i][j] == 'X') {wall ++;}//统计墙的数量
   }
   getchar();
  }
  if (n * m - wall <= time) { //在迷宫里用的最大时间没有规定时间多的情况
   puts("NO");
   continue;
  }
  M[si][sj] = 'X';
  search(si, sj, 0);
  if (isfind) {
   puts("YES");
  }else {
   puts("NO");
  }
 }
 return 0;
}