时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
一农场由图所示的十一种小方块组成，蓝色线条为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。
输入：
给出若干由字母表示的最大不超过50×50具体由(m，n)表示，的农场图
输出：
编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。
输入样例：
2 2
DK
HF
3 3
ADC
FJK
IHE
-1 -1
输出样例：
2
3
提示：
参考迷宫问题，实现时关键要解决好各块的表示问题。
#include<iostream> using namespace std; class BaseDate { public:bool geted;//存放当前的块是否被取char ch;//存放相应的字母int left,right,up,down;//存放是否有连通线init(bool g=false,char c=' ',int l=0,int r=0,int u=0,int d=0);//有默认构造函数 }; BaseDate::init(bool g,char c,int l,int r,int u,int d)//默认构造函数 {geted=g; ch=c; left=l; right=r; up=u; down=d; } void readdata(); void search(int ,int); int canplace(int row,int col,int r,int c); void printresult(); BaseDate Array[50][50]; int R,C; int NUM[15];//存储15种不同的农场打井数 int kk=0;int main() {int num=0;readdata();while(R!=-1||C!=-1){for(int i=0;i<R;i++)for(int j=0;j<C;j++)if(Array[i][j].geted==false) { search(i,j); num++; }NUM[kk++]=num;num=0;readdata();}printresult();return 0; } void printresult() {for(int i=0;i<kk;i++)printf("%d\n",NUM[i]); } void readdata() { cin>>R>>C; //m表示行数，n表示列数for(int i=0;i<R;i++)for(int j=0;j<C;j++) { Array[i][j].geted=false;//重复使用全局变量Array[50][50]Array[i][j].left=0; Array[i][j].right=0; Array[i][j].up=0; Array[i][j].down=0; cin>>Array[i][j].ch; switch(Array[i][j].ch){ case'A': Array[i][j].left=1;Array[i][j].up=1; break;case'B': Array[i][j].right=1;Array[i][j].up=1; break;case'C': Array[i][j].left=1;Array[i][j].down=1; break;case'D': Array[i][j].right=1;Array[i][j].down=1; break;case'E': Array[i][j].up=1;Array[i][j].down=1; break;case'F': Array[i][j].left=1;Array[i][j].right=1; break;case'G': Array[i][j].left=1;Array[i][j].right=1; Array[i][j].up=1; break;case'H': Array[i][j].left=1;Array[i][j].up=1; Array[i][j].down=1; break;case'I': Array[i][j].left=1;Array[i][j].right=1; Array[i][j].down=1; break;case'J': Array[i][j].right=1;Array[i][j].up=1; Array[i][j].down=1; break;case'K': Array[i][j].left=1;Array[i][j].right=1;Array[i][j].up=1; Array[i][j].down=1; break;default: printf("error");}} } void search(int row,int col) {int r,c;Array[row][col].geted=true;r=row; c=col-1;//左if(canplace(row,col,r,c))search(r,c);r=row+1; c=col;//下if(canplace(row,col,r,c))search(r,c);r=row; c=col+1;//右if(canplace(row,col,r,c))search(r,c);r=row-1; c=col;//上if(canplace(row,col,r,c))search(r,c); } int canplace(int row,int col,int r,int c) {if(r>=0 &&r<R &&c>=0 &&c<C &&Array[r][c].geted==false){if(r==row &&c==col-1 &&Array[row][col].left==1 &&Array[r][c].right==1) //判左return 1;if(r==row+1 &&c==col &&Array[row][col].down==1 &&Array[r][c].up==1)//判下return 1;if(r==row &&c==col+1 &&Array[row][col].right==1 &&Array[r][c].left==1)//判右return 1;if(r==row-1 &&c==col &&Array[row][col].up==1 &&Array[r][c].down==1)//判上return 1;}return 0; }
