卫星照片 (Standard IO)

题目：

农夫 John 正在研究他的农场的卫星照片.照片为一个R (1 <=R <= 75) 行 C (1 <= C <= 75) 列的字符矩阵表示.如下图: 　　……………… 　　..#####…….##.. 　　..#####……##… 　　……………… 　　#…….###…..#. 　　#…..#####…….

　　图上的一块相连通的 “#” 表示一群奶牛或一个房间, 两个子”#” 连通的意思是说左右或上下相连.而下面的两块则是分开的: 　　…. 　　.#.. 　　..#. 　　….

　　John现在根据卫星照片上的的这些”#”块的形状来判断哪些是牛群,哪些是房间.如果一个”#”块形状一个内部和边全部都是“#”的矩形,则是房间，如果一个连通块只有一个“#”,也是房间.其它的则认为都是牛群.在第一个图中,有三个房间 ( 2x1, 2x5, and 1x1)和2群牛. 　　请根据输入文件中的数据,统计出房间数和牛群数.数据中牛群不会包围另一个牛群或房间.

思路：记忆化深搜

#include<iostream> #include<cstdio> using namespace std; bool a[100][100]; int ans1,ans2; bool check(int xx,int yy) { if (a[xx+1][yy]||a[xx-1][yy]||a[xx][yy+1]||a[xx][yy-1]) return true; return false; } void dfs(int q,int p) { a[q][p]=false; if (a[q+1][p]) dfs(q+1,p); if (a[q-1][p]) dfs(q-1,p); if (a[q][p+1]) dfs(q,p+1); if (a[q][p-1]) dfs(q,p-1); } void cc(int x,int y) { int l=x,r=y; while (a[l][y]) l++; while (a[x][r]) r++; l--; r--; for (int i=x;i<=l;i++) for (int j=y;j<=r;j++) if (a[i][j]==false) { dfs(x,y); ans2++; return; } for (int i=x;i<=l;i++) for (int j=y;j<=r;j++) a[i][j]=false; for (int i=x;i<=l;i++) for (int j=y;j<=r;j++) if (check(i,j)) { for (int i=x;i<=l;i++) for (int j=y;j<=r;j++) a[i][j]=true; dfs(x,y); ans2++; return; } ans1++; return; } int main() { int n,m; char c; scanf("%d%d\n",&n,&m); for (int i=1;i<=n;i++,getchar()) for (int j=1;j<=m;j++) { c=getchar(); if (c=='#') a[i][j]=true; if (c=='.') a[i][j]=false; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (a[i][j]) cc(i,j); printf("%d\n",ans1); printf("%d\n",ans2); }