不太一样的搜索水题

题意:
A–K对应不同水管 要事整个田地都能灌溉到水 ,问 需要到少水源

思路:
一开始想的就是深搜 只是方向都不同罢了 和求连通区域个数没什么区别 属于最水的搜索题

AC Code

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

using namespace std;
const int maxn=60;
char mat[maxn][maxn];
bool vis[maxn][maxn];
int row,col;
int dir[12][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}
};
int dx[]= {-1,0,1,0};
int dy[]= {0,1,0,-1};

bool judge(int x,int y)
{
    return x>0&&x<=row&&y>0&&y<=col&&!vis[x][y];
}

void dfs(int from,int x,int y)
{
    int num=mat[x][y]-'A',xx,yy;
    if(from<4)
        if(!dir[num][(from+2)%4]){vis[x][y]=false; return ;}
    for(int i=0; i<4; i++)
    {
        if(dir[num][i])
        {
            xx=x+dx[i];
            yy=y+dy[i];
            if(judge(xx,yy))
            {
                vis[xx][yy]=true;
                dfs(i,xx,yy);
            }
        }
    }
}

int main()
{
    while(scanf("%d%d",&row,&col),row>0&&col>0)
    {
        getchar();
        for(int i=1; i<=row; i++)
            scanf("%s",mat[i]+1);
        memset(vis,false,sizeof vis);
        int ans=0;
        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++)
                if(!vis[i][j])
                {
                    ans++;
                    vis[i][j]=true;
                    dfs(maxn,i,j);
                }
        printf("%d\n",ans);
    }
    return 0;
}