zoj 2110 Tempter of the Bone ——DFS+剪枝

April 6, 2013
zoj DFS

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1110 题意：　　给一个矩阵，‘X’代表墙壁，‘.’代表空格，‘S’代表起始位置，‘D’代表终点。从起点开始，每个空格只许经过一次，求在规定的时间t的时候，能否正好到达终点。每走一个花费1个单位时间。输入n,m,t，分别代表矩阵的行，列，规定的时间。思路：　　深度优先搜索，从起点开始，按照四个方向搜索，判断某个方向的下一个方格如果不是墙壁的话，就把它标为墙壁，然后从这个点继续往下搜索，如果从这个点往下搜索失败后，就要把这个点标记回原来的空格符号：‘.’。然后尝试下一个方向。直到i == di, j == dj, t == T的时候，表示搜索成功，flag = true; return; 其中si sj 是起点位置，di dj是终点位置，T是当前所花费的时间。　　然后还有几处剪枝：如果这个矩阵的空格的数目小于等于时间t，那么不可能成功。这在主函数里面可以剪枝。在dfs的过程中，如果发现剩余的时间小于当前位置到终点的最小距离，可以直接判断搜索失败；如果剩余的时间和当前位置到终点的最小时间的差值是奇数的话，可以判断搜索一定失败，可以剪枝，如果是偶数的话，则可能成功。　　今天突然发现，以前写的解题报告太搓了……向kedebug的博客学习，O(∩_∩)O哈哈~加油


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;

bool flag;
char s[9][9];
int t, n, m, si, sj, di, dj;
int dir[4][4] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
void dfs(int i, int j, int T){
  if (i == di && j == dj && T == t){
    flag = true; return;
  }
  if (i <= 0 || j <= 0 || i > n || j > m) return;
  int temp = t - T - abs(i-di) - abs(j-dj);
  if (temp < 0 || temp&1)return;
  for (int k = 0; k < 4; ++k){
    if (s[i+dir[k][0]][j+dir[k][1]] != 'X'){
      s[i+dir[k][0]][j+dir[k][1]] = 'X';
      dfs(i+dir[k][0], j+dir[k][1], T+1);
      if (flag) return;
      s[i+dir[k][0]][j+dir[k][1]] = '.';
    }
  }
  return;
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("zoj2110.in", "r", stdin);
#endif
  while (~scanf("%d%d%d", &n, &m, &t) && m+n+t){
    getchar();
    int wall = 0;
    for (int i = 1; i <= n; ++i){
      for (int j = 1; j <= m; ++j){
        scanf("%c", &s[i][j]);
        if (s[i][j] == 'S'){
          si = i; sj = j;
        }
        else if (s[i][j] == 'D'){
          di = i; dj = j;
        }
        else if (s[i][j] == 'X') wall++;
      }
      getchar();
    }
    if (m * n - wall <= t){
      printf("NO\n"); continue;
    }
    flag = false;
    s[si][sj] = 'X';
    dfs(si, sj, 0);
    if (flag) printf("YES\n");
    else printf("NO\n");
  }

  return 0;
}

开始敲的有错误，怎么也找不出来，然后急了，重新写了一遍，对了……代码能力，准确度有木有！！还有一点，就是这种读字符的题目，并且是一个一个字符读的，每行要用一个getchar()吸收换行符。并且读字符之前也要用一个getchar()吸收之前读数字的换行符，这个地方特别容易出错。

Read more