1198 ( Farm Irrigation )

Problem : 1198 ( Farm Irrigation )     Judge Status : Accepted

 

 
其实这道题勘探油田的变形，只是判断两个格子是否连通的规则有所变化。原先我用了一个三维数组G[i][j][k]=1来表示当图j在图i的k反向
时两图连通，可是这样表示很麻烦要11幅图与11幅图一一进行对比而且容易出错，后来改用了下面check里的方法，简化了很多。G[i][k]表示
第i幅图有水管的走向为k方向，如果与它相邻的G[j][(k+2)%4]=1,则两图连通

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int vis[51][51],G[11][4]={{1,0,0,1},{1,1,0,0},{0,0,1,1},{0,1,1,0},
                          {1,0,1,0},{0,1,0,1},{1,1,0,1},{1,0,1,1},
                          {0,1,1,1},{1,1,1,0},{1,1,1,1}};
string a[51];
int m,n;
int dir[4][2]={-1,0,0,1,1,0,0,-1};
bool check(char s1,char s2,int d)
{
    if(G[s1-'A'][d]&&G[s2-'A'][(d+2)%4])return 1;
    return 0;
}
void DFS(int i,int j)
{
    vis[i][j]=1;
    for(int k=0;k<4;k++)
    {
        int x=i+dir[k][0];
        int y=j+dir[k][1];
        if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&check(a[i][j],a[x][y],k))
        {
            DFS(x,y);
        }
    }
    return ;
}
int main()
{
    
    while(cin>>m>>n)
    {
        if(m<0||n<0)break;
        
        memset(vis,0,sizeof(vis));
        for(int i=0;i<m;i++)
        {
            cin>>a[i];
        }
        int num=0;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
            {
                if(!vis[i][j])
                {
                    num++;DFS(i,j);
                }
            }
            cout<<num<<endl;
    }
}