農場灌

時間:1000 msメモリ制限:10000 K合計時間:3000 ms
説明:1つの農場は図に示す11種類の小さなブロックからなり、青い線は灌隣接する2つの灌
入力:アルファベットで表される最大50を超えないものをいくつか与えます.×50具体的には(m,n)で表される、農場図
出力:プログラミングして最小必要な井戸数を求める.各測定例の出力は1行を占める.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
",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;

}