Farm Irrigation

题目链接：杭电oj 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.

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

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.

输入：

There are several test cases! In each test case, the first line contains 2 integers M and N, then M lines follow. In each of these lines, there are N characters, in the range of 'A' to 'K', denoting the type of water pipe over the corresponding square. A negative M or N denotes the end of input, else you can assume 1 <= M, N <= 50.

输出：

For each test case, output in one line the least number of wellsprings needed.

样例输入：

2 2

3 3

ADC

FJK

IHE

-1 -1

样例输出：

代码：

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#define MAX 55
using namespace std;
char map[MAX][MAX];
int judge[MAX][MAX]={0}; 
int N,M;
int ans;//水源个数 
int square[11][4]={
						{1,0,0,1},//A	0
						{1,1,0,0},//B	1
						{0,0,1,1},//C	2
						{0,1,1,0},//D	3
						{1,0,1,0},//E	4
						{0,1,0,1},//F	5
						{1,1,0,1},//G	6
						{1,0,1,1},//H	7	
						{0,1,1,1},//I	8
						{1,1,1,0},//J	9
						{1,1,1,1},//K	10
				  };	
				  //定义管道的11种结构 
				  
int dir[4][2]={
					{-1,0},//上 
					{0,1},//右 
					{1,0},//下 
					{0,-1},//左 
			  };
			  //定义4个搜索方向 
		  
typedef struct Element
{
    int x;
    int y;
    char elem;
}Element; //以结构体来存元素的信息 

Element elem;
Element elem_deal;
queue<Element> q;//定义队列容器用以处理数据 
Element x;

void drow_map()			//录入地图 
{
	int i,j;
    for(i=0;i<N;i++)
    {
        getchar();
        for(j=0;j<M;j++)
        {
            cin>>map[i][j];
        }    
    }
    
}

void print()		//输出处理过后的数据，此题无需用到 
{
	int i,j;
	for(i=0;i<N;i++)
    {
        for(j=0;j<M;j++)
        {
            cout<<judge[i][j];
        }    
        cout<<endl;
    }
    cout<<endl;
}

void queue_deal(Element x)	//利用队列来对农场管道进行处理 
{
	int i,j,t;
    q.push(x);
    while(!q.empty())
    {
        elem=q.front();		//取队首元素 
        judge[elem.x][elem.y]=ans;//把能连通的区域用同一数值表示 
        q.pop();			//队首元素出队 
        {
            for(i=0;i<4;i++)
            {
            	t=i+2;//用以判断缺口 
            	if(square[elem.elem-'A'][i]==0)		//判断管道是否在此方向有缺口 
				{
					continue;
				}
				else
				{
					elem_deal.x=elem.x+dir[i][0];
					elem_deal.y=elem.y+dir[i][1];
					if(elem_deal.x<N&&elem_deal.x>=0&&elem_deal.y<M&&elem_deal.y>=0&&judge[elem_deal.x][elem_deal.y]==0)
					//判断是否越界或被处理过 
					{
						elem_deal.elem=map[elem_deal.x][elem_deal.y];
						if(t>=4)
						t=t%4;
						if(square[elem_deal.elem-'A'][t]==1)//判断被连接的管道是否在相反的方向有缺口 
						q.push(elem_deal);
					}
				}  
            }
        }
	
    }
    ans++;
}

void deal()		//处理 
{
	int i,j;
    ans=1;
    for(i=0;i<N;i++)
    for(j=0;j<M;j++)
    {
        if(judge[i][j]==0)
        {
            x.x=i;
            x.y=j;
            x.elem=map[i][j];
            queue_deal(x);
        }
		else
		continue;        
    }
}

int main()
{
    while(1)
    {
        cin>>N>>M;
        if(N==-1&&M==-1)
        break;
        drow_map();
        deal();
        cout<<ans-1<<endl;
        memset(map,'0',sizeof(map));
        memset(judge,0,sizeof(judge));
    }
return 0;
}

杭电oj-----Farm Irrigation(BFS)