学步园

题意：A-K分别代表不同的水管接口，问有多少个不联通的水管。

思路：暴搜

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;
const int N = 59;
int n,m;
char map[N][N];
int num[]={2,2,2,2,2,2,3,3,3,3,4};
int mm[][5]={
    {0,1},
    {0,3},
    {1,2},
    {2,3},
    {0,2},
    {1,3},
    {0,1,3},
    {0,1,2},
    {1,2,3},
    {0,2,3},
    {0,1,2,3}
};
void init()
{
    for(int i=1;i<=n;i++)
    scanf("%s",map[i]+1);
}
bool oor(int x,int y)
{
    if(x<1||x>n) return false;
    if(y<1||y>m) return false;
    return true;
}
int dx[] ={-1,0,1,0};
int dy[] ={0,-1,0,1};
void dfs(int x,int y)
{

    if(!oor(x,y)||map[x][y]=='O') return ;
    //cout<<x<<" "<<y<<endl;
    int k = map[x][y]-'A'; map[x][y] = 'O';
    for(int i=0;i<num[k];i++)
    {
        int tx = x+dx[mm[k][i]],ty = y+dy[mm[k][i]];
        if(!oor(tx,ty)||map[tx][ty]=='O') continue;
        int kk=map[tx][ty]-'A';
        //cout<<"* "<<tx<<" "<<ty<<endl;
        for(int j=0;j<num[kk];j++)
        if((mm[k][i]!=mm[kk][j])&&((mm[k][i]+mm[kk][j])%2)==0)
        dfs(tx,ty);
    }
}
void solve()
{
    int ans=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(map[i][j]!='O')
    dfs(i,j),ans++;
    printf("%d\n",ans);
}
int main()
{
    freopen("in.txt","r",stdin);
    while(~scanf("%d%d",&n,&m)&&(n+m)>=0)
    {
        init();
        solve();
    }
    return 0;
}