Sample Input 10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W. Sample Output 3
每个点与其周围的8个可以看作同一堆
算法：
1.遍历每个点，如果它没有被访问过，并且有水，则它入栈，并且标记为已访问
2.只要栈不空，依次访问栈顶元素的邻居，如果邻居有水并且没有被访问过，则邻居入栈，如果邻居都没有水，则出栈；如果栈空了，则水堆数加1
#include <stack> using namespace std; typedef struct { int x,y; }Point1; int main() { int w,h; //int x,y; char c; int s[101][101]; stack<Point1> sta; scanf("%d%d",&h,&w); getchar(); int i,j; for(i=0;i<h;i++) { for(j=0;j<w;j++) { scanf("%c",&c); if(c=='.')s[i][j]=0; else if(c=='W') s[i][j]=1; } getchar(); } int count=0; int num=0; for(i=0;i<h;i++) for(j=0;j<w;j++) if(s[i][j]==1){ Point1 p1; p1.x=i; p1.y=j; sta.push(p1); s[i][j]=2; count=0; while(!sta.empty()) { Point1 p=sta.top(); if((p.x-1)>=0&&s[p.x-1][p.y]==1) { Point1 t; t.x=p.x-1; t.y=p.y; sta.push(t); count++; p=t; s[t.x][t.y]=2; }else if(p.x>=0&&p.x<h&&p.y-1>=0&&p.y<w&&s[p.x][p.y-1]==1) { Point1 t; t.x=p.x; t.y=p.y-1; sta.push(t); count++; s[p.x][p.y-1]=2; p=t; } else if(p.x+1<h&&p.x>=0&&p.y>=0&&p.y<w&&s[p.x+1][p.y]==1) { Point1 t; t.x=p.x+1; t.y=p.y; sta.push(t); count++; s[p.x+1][p.y]=2; p=t; } else if(p.x<h&&p.x>=0&&p.y>=0&&p.y+1<w&&s[p.x][p.y+1]==1) { Point1 t; t.x=p.x; t.y=p.y+1; sta.push(t); count++; s[p.x][p.y+1]=2; p=t; }else if(p.x-1>=0&&p.y-1>=0&&s[p.x-1][p.y-1]==1) { Point1 t; t.x=p.x-1; t.y=p.y-1; sta.push(t); count++; p=t; s[t.x][t.y]=2; } else if(p.x+1<h&&p.y+1<w&&s[p.x+1][p.y+1]==1) { Point1 t; t.x=p.x+1; t.y=p.y+1; sta.push(t); count++; p=t; s[t.x][t.y]=2; }else if(p.x+1<h&&p.y-1>=0&&s[p.x+1][p.y-1]==1) { Point1 t; t.x=p.x+1; t.y=p.y-1; sta.push(t); count++; p=t; s[t.x][t.y]=2; }else if(p.x-1>=0&&p.y+1<w&&s[p.x-1][p.y+1]==1) { Point1 t; t.x=p.x-1; t.y=p.y+1; sta.push(t); count++; p=t; s[t.x][t.y]=2; } else sta.pop(); } num++; } printf("%d\n",num); return 0; }