HF
3
//这题可以把图中的每一个放格的连通性表示出来，以上下左右 能连通即为1反之为0 在dfs搜索
//本来想练下并查集 结果没想出来。。
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
//上下左右
int n,m; //矩阵大小
int vis[550][550]; //标记数组
int dir[4][2]={-1,0,1,0,0,-1,0,1}; //方向
int a[11][4]={
1,0,1,0,
1,0,0,1,
0,1,1,0,
0,1,0,1,
1,1,0,0,
0,0,1,1,
1,0,1,1,
1,1,1,0,
0,1,1,1,
1,1,0,1,
1,1,1,1,
}; //11个字母的出口 上下左右 有出口为1 没有为0
struct Node
{
int n;
int a,b,c,d; //上下左右
}ma[550][550];
void dfs(int xx,int yy)
{
if(vis[xx][yy]) return;
vis[xx][yy]=1;
if((xx<0&&xx>=n)||(yy<0&&yy>=m))return;
for(int i=0;i<4;i++)
{
int x1,y1;
x1=xx,y1=yy;
x1+=dir[i][0];
y1+=dir[i][1];
if(x1>=0&&x1<n&&y1>=0&&y1<m) //边界
{
if(i==0&&(ma[xx][yy].a+ma[x1][y1].b==2))
{
dfs(x1,y1);
}
else if(i==1&&(ma[xx][yy].b+ma[x1][y1].a==2))
{
dfs(x1,y1);
}
else if(i==2&&(ma[xx][yy].c+ma[x1][y1].d==2))
{
dfs(x1,y1);
}
else if(i==3&&(ma[xx][yy].d+ma[x1][y1].c==2))
{
dfs(x1,y1);
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==-1&&m==-1) break;
char c;
for(int i=0;i<n;i++)
{
for(int k=0;k<m;k++)
{
cin>>c;
ma[i][k].n=c-'A';
}
}
int cnt=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
for(int k=0;k<m;k++)
{
ma[i][k].a=a[ma[i][k].n][0],ma[i][k].b=a[ma[i][k].n][1];
ma[i][k].c=a[ma[i][k].n][2],ma[i][k].d=a[ma[i][k].n][3];
}
for(int i=0;i<n;i++)
{
for(int k=0;k<m;k++)
{
if(!vis[i][k])
{
cnt++;
dfs(i,k);
}
}
}
printf("%d\n",cnt);
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/a73265/article/details/46888955