不太一样的搜索水题
题意：
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;
}