poj_1164_递归

题目描述：

   给出一个方格描述，其中有些格子互通。求最大互通格子的长度，和一共不互通的格子数目。

解题思路：

   求最大互通格子长度，既dfs，可以递归做，结束条件为该格子已经被走过。数有多少个不互通格子，遍历即可。

代码：

#include <stdio.h>
#include <stdlib.h>
#define N 51typedef struct{int w,n,e,s;
}ROOM; //有墙则置为1, 无墙为0 ROOM room[N][N];
int f[N][N], s, max, count, m, n;void find(int i, int j)
{if(f[i][j] >0 ){;}else{s++;f[i][j] = count + 1;//四个方向 if(room[i][j].w == 0)find(i,j-1);if(room[i][j].n == 0)find(i-1,j);if(room[i][j].s == 0)find(i+1,j);if(room[i][j].e == 0)find(i,j+1);}  
}
main()
{int i,j,v;scanf("%d %d",&m, &n);for(i=0;i<m;i++)for(j=0;j<n;j++){scanf("%d",&v);room[i][j].s = v/8;v = v%8;room[i][j].e = v/4;v = v%4;room[i][j].n = v/2;v = v%2;room[i][j].w = v/1;}memset(f,0,sizeof(f));max = 0;count = 0;for(i=0;i<m;i++){for(j=0;j<n;j++){if(f[i][j]==0){s = 0;find(i,j);count ++;}if(s>max)max = s;}}printf("%d\n",count);printf("%d\n",max);//system("pause");return 0;
}