poj1272 棋盘问题 ——DFS入门题

May 13, 2013
POJ DFS

题目链接：http://poj.org/problem?id=1321 题目大意：　　中文题，省了…… 题目思路：　　感觉搜索题目还是要多做，很多东西都是开始看起来很复杂，其实根本就没有那么复杂，比如说这道，实际上就比较基础，可是，自己还是做不出来……o(╯□╰)o 　　这道题目需要注意的一点就是：先DFS一行，然后要注意，要考虑当前行不放，直接DFS下一行！这个情况赶脚还是比较不容易想到的，虽然做完之后感觉也挺自然啊，可是……当初为毛想不到。。。就是思维的问题吧……代码看的是这位仁兄的：http://fuliang.iteye.com/blog/398700ＴＨＸ……＾＿＾


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#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 =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
const int MAX = 10;
char m[MAX][MAX];int cnt, n, k, sum;
bool p[MAX];
bool judge(int i, int j) {
  if (p[j] == false && m[i][j] == '#') return true;
  else return false;
}
void dfs(int x) {
  if (sum == k) {cnt++; return;}
  if (x >= n) return;
  int i;
  for (i = 0; i < n; ++i) {
    if (judge(x, i)) {
      p[i] = true; sum++; dfs(x+1);
      p[i] = false; sum--;
    }
  }
  dfs(x + 1);
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj1321.in", "r", stdin);
#endif
  while (~scanf("%d%d", &n, &k)) {
    int i, j;
    if (k == -1 && n == -1) break;
    //getchar();
    for (i  = 0; i <n ; ++i) {
      for (j = 0; j < n; ++j) {
        //scanf("%c", &m[i][j]);
        cin>>m[i][j];
      }
      //getchar();
    }
    cnt = 0;
    memset(p, false, sizeof(p));
    sum = 0;
    dfs(0);
    printf("%d\n", cnt);
  }

  return 0;
}

还有一个地方不懂……就是注释的那三行，如果把那三行的注释符号去掉，再把cin那一行删掉，也是可以过的。就是不明白为什么用scanf()读入一行一行的字符串也需要用getchar()？当初纠结好久……原来连读入都没有处理好…… 还有就是，这题过了以后，为了测试一下加getchar()是不是也可以过，然后就是各种WA啊……就不明白了，为什么刚才还可以过的代码，现在就WA了……好吧……后来才发现因为开了许多窗口，交错题了ｏ（╯□╰）ｏ多么奇葩的错误……

Read more