题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1198

题目描述

Benny has a spacious farm land to irrigate. The farm land is a rectangle, and is divided into a lot of samll squares. Water pipes are placed in these squares. Different square has a different type of pipe. There are 11 types of pipes, which is marked from A to K, as Figure 1 shows.
http://acm.hdu.edu.cn/data/images/1121-1.gif

Benny has a map of his farm, which is an array of marks denoting the distribution of water pipes over the whole farm. For example, if he has a map

ADC
FJK
IHE

then the water pipes are distributed like
http://acm.hdu.edu.cn/data/images/1121-2.gif

Several wellsprings are found in the center of some squares, so water can flow along the pipes from one square to another. If water flow crosses one square, the whole farm land in this square is irrigated and will have a good harvest in autumn.

Now Benny wants to know at least how many wellsprings should be found to have the whole farm land irrigated. Can you help him?

Note: In the above example, at least 3 wellsprings are needed, as those red points in Figure 2 show.

思路

因为刷到并查集了,这题当然也是并查集。

先把A-K这11中连接情况用数组表示出来,以上0左1右2下3的顺序,0表示无管道,1表示有,方便后面判断是否连接。

然后进行判断,因为上+下=3,左加右=3,那么只要3-一个方向就是对面那个方向。

AC后感觉可以用DFS来做,结果超时,改成BFS,0ms过。现在想想改成DFS并没有什么意义= =因为搜索方式差不多只是路径不同。。。

AC代码

/*************************************************************************
    > File Name: 1198_2.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-07-05 Sun 17:09:25 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

const int _max = 50*50+1;
bool pipes[11][4] = { // 上0左1右2下3,0表示无管道,1表示有
    1,1,0,0, // A
    1,0,1,0, // B
    0,1,0,1, // C
    0,0,1,1, // D
    1,0,0,1, // E
    0,1,1,0, // F
    1,1,1,0, // G
    1,1,0,1, // H
    0,1,1,1, // I
    1,0,1,1, // J
    1,1,1,1  // K
};
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0}; // 上0 左1 右2 下3
int Set[_max]; // 集合,能连接的区域放在一个集合中
char Map[51][51]; // 地图
bool visited[51][51]; // 记录某块区域是否访问过
int n, m; // 地图大小宽,高

int find(int x) {
    return x==Set[x]?x:Set[x]=find(Set[x]);
}
void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if(a!=b)
        Set[a] = b;
}

// void DFS(int i, int j) { // DFS超时= =
    // if(i<1 || i>m || j<1 || j>n)
        // return;
    // visited[i][j] = true;
    // for(int k=0; k<4; ++k) { // 上0左1右2下3
        // int nx = i+dx[k];
        // int ny = j+dy[k];
        // if(nx>=1 && nx<=m && ny>=1 && ny<=n&&!visited[nx][ny]) {
            // if(pipes[Map[i][j]-'A'][k] && pipes[Map[nx][ny]-'A'][3-k]) {
                // unite((i-1)*n+j, (nx-1)*n+ny);
            // }
            // DFS(nx, ny);
            // visited[nx][ny] = false;
        // }
    // }
// }

void BFS(int i, int j) {
    struct pos{ // 区域信息
        int x, y;
        pos(int x, int y): x(x),y (y){}
    };
    queue<pos> q;
    q.push(pos(i, j)); // 当前区域入队
    visited[i][j] = true; // 标记当前区域
    while(q.size()) {
        pos s = q.front();
        q.pop();
        if(s.x == m && s.y==n) // 到达终点结束搜索
            break;
        for(int k=0; k<4; ++k) {
            int nx = s.x+dx[k]; // 下一个区域坐标
            int ny = s.y+dy[k];
            if(nx >=1 && nx<=m && ny>=1 && ny<=n) { // 区域在地图中
                if(pipes[Map[nx][ny]-'A'][3-k] && pipes[Map[s.x][s.y]-'A'][k]) // 若相邻两块区域能连接
                    unite((s.x-1)*n+s.y, (nx-1)*n+ny); // 放到一个集合中
                if(!visited[nx][ny]) { // 下一个区域若未访问则入队
                    q.push(pos(nx,ny));
                    visited[nx][ny] = true;
                }
            }
        }
    }

}

int main()
{
#ifdef Oj
    freopen("1198.in", "r", stdin);
#endif
    while(scanf("%d%d", &m, &n) == 2 && (n>=0 && m>=0)) {
        getchar();
        for(int i=m*n; i>=1; --i)
            Set[i] = i;
        memset(visited, 0, sizeof(visited));
        for(int i=1; i<=m; ++i) {
            for(int j=1; j<=n; ++j)
                Map[i][j]=getchar();
            getchar();
        }

        BFS(1, 1);

        // for(int i=1; i<=m; ++i) // 原始算法,和BFS只是搜索路径上的区别 = =BFS是副对角线方向搜索,这里是一行一行搜索。
            // for(int j=1; j<=n; ++j)
                // for(int k=0; k<4; ++k) {
                    // int nx = i+dx[k];
                    // int ny = j+dy[k];
                    // if(nx >= 1 && nx <=m && ny>=1 && ny<=n) {
                        // if(pipes[Map[nx][ny]-'A'][3-k] && pipes[Map[i][j]-'A'][k])
                            // unite((i-1)*n+j, (nx-1)*n+ny);
                    // }
                // }

        int ans = 0;
        for(int i=m*n; i>=1; --i)
            if(Set[i]==i)
                ++ans; // 集合数量即为水源数量。
        printf("%d\n", ans);
    }
    return 0;
}