从任意的W开始，不停地把邻接的部分用'.'代替。1次DFS后与初始的这个W连接的所有W就都被替换成了'.'，因此直到图中不再存在W为止，总共进行DFS的次数就是答案了。8个方向共对应了8种状态转移，每个格子作为DFS的参数至多被调用一次，所以复杂度为O(8×N×M)=O(N×M)。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; char map[110][110]; int dis[8][2]={{0,1},{1,0},{-1,0},{0,-1},{1,1},{-1,-1},{-1,1},{1,-1}}; int n,m; void dfs(int x,int y) { map[x][y]='.'; for(int i=0;i<8;i++) { int xx=x+dis[i][0]; int yy=y+dis[i][1]; if(xx<0||xx>=n||yy<0||yy>=m) continue; if(map[xx][yy]=='W') { dfs(xx,yy); } } return; } int main() { //freopen("d:\\test.txt","r",stdin); while(cin>>n>>m) { for(int i=0;i
      
       >map[i][j]; } } int ans=0; for(int i=0;i