zoj 2412 Farm Irrigation ——DFS入门题

April 7, 2013
zoj DFS

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1412 题意：　　有11种正方形，每种正方形里面对应一种形状的水管，不同的的正方形一用A到K表示，给一个矩阵，问至少需要多少个水源可以使矩形中所有的地方都可以被灌溉，如果两个相邻的正方形的水管正好对口，那么这两个正方形可以共用一个水源。思路：　　开始感觉很复杂，明显可以DFS做，但是感觉比较麻烦，关键是怎么处理题目中的条件。　　首先，处理11种不同的水管，分4个方向，1表示有接口，0表示没有接口。用一个二维数组存所有种类的水管。　　然后，把输入的字符转化成数字，可以再输入的时候边输入边处理，用字符减去字符“A”就可以了，对应的上面给11中不同水管中的一种。以上这两个处理方法要注意，学习一下，稍微看了一下别人的代码才想到的。这种看似比较简单的处理，往往给解题带来比较大的方便。　　最后，就是如何深搜了。这个要考虑清楚。用一个flag二维数组表示是否访问过这个方格。深搜的时候，如果访问到它时，先判断它是否被访问过，然后立刻标记为已访问。然后就是判断当前方格的四个方向是不是有接口，如果某个方向有接口的话，就判断这个方向上的下一个方格中，和当前方格相邻的边是不是有接口，如果有接口，则继续深搜这个相邻的点。这里有个处理：（k+2）%4，意味着，比如：当前方格如果右边有接口，则判断右边的方格的左边的边是不是有接口，其它情况一样。然后就是主函数里面的dfs外面的for循环，思想和以前做过的zoj 1709是一样的，就是搜到某个点的时候，用一个mrk标记一下，把和它有关系的点都搜完，如果有符合条件的，mrk会改变，然后就cnt++用来计数，这种题目是相似的，都是要求符合条件的点相邻。　　有一个细节，就是矩阵的数组还是从1开始吧，数组稍微开大一点儿，这样在深搜下一个方向的时候，就不会因为数组越界出错了。这个问题以前没有注意到。


#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;

int grid[11][4] = {{0,0,1,1},{1,0,0,1},{0,1,1,0},{1,1,0,0},{0,1,0,1},
  {1,0,1,0},{1,0,1,1},{0,1,1,1},{1,1,1,0},{1,1,0,1},{1,1,1,1}};
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
bool flag[55][55];
int s[55][55];
bool mrk = false;
int n, m;
void dfs(int i, int j){
  if (i <= 0 || i > m || j <= 0 || j > n) return;
  if (flag[i][j]) return;
  mrk = true; flag[i][j] = true;
  for (int k = 0; k < 4; ++k){
    if (grid[s[i][j]][k] && grid[s[i+dir[k][0]][j+dir[k][1]]][(k+2)%4]){
      dfs(i+dir[k][0], j+dir[k][1]);
    }
  }
  return;
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("zoj2412.in", "r", stdin);
#endif
  while (~scanf("%d%d", &m, &n)){
    if (m+n<0) break; char ch; getchar(); int cnt = 0;
    for (int i = 1; i <= m; ++i){
      for (int j = 1; j <= n; ++j){
        scanf("%c", &ch);
        s[i][j] = ch-'A';
      } getchar();
    }
    memset(flag, false, sizeof(flag));
    for (int i = 1; i <= m; ++i){
      for (int j = 1;j <= n; ++j){
        mrk = false;
        if (!flag[i][j]) dfs(i, j);
        if (mrk) cnt++;
      }
    }
    printf("%d\n", cnt);
  }

  return 0;
}

竟然1A了……

Read more