【深捜し(DFS)-例題-踏青】-C++

1427 ワード

  

                   。                       ,        ,     。         4                ,              ,                  。   '#'    ,'.'    ,        2    。

##..

..##

         2         ,           。            ,        ,         ,            。


  
      n, m (1 ≤ n,m ≤ 100)       。

      n            。


  
         。


     1 

5 6
.#....
..#...
..#..#
...##.
.#....
     1

5

この問題は典型的な深捜し(くだらない話)では、なぜ深捜しを使うことを考えているのでしょうか.まずもう一度テーマをよく見てみましょう(純粋にコードを取りに来たわけではないならそうしたほうがいいです)
はい、この問題は問題の意味をはっきり見てから、どれだけの草むらを出力しますか.草むらは1枚か数枚の隣接する草で構成されている注意です!隣接していなければなりません!ここの隣接は、周囲の4つの方向を指します.では典型的な深捜しです(今回はくだらない話ではありません)
どうやって?まず原図を入力して、それから二重に繰り返して、'#'文字はそれを普通のものにします'.それから周りに広がって、草を見つけたらリサイクルして、この草がいる草むらの中のすべての草が空き地になるまで、ans++します.コード実装は簡単です(DFSのコードは一般的に短いです)
コードは次のとおりです.
#include
using namespace std;
char s[110][110];
int n,m,sum;
int dir[4][2] = {{1,0}, {0,1}, {-1,0},{0,-1}};
int vis[110][110];//={0};
void dfs(int x,int y){
	int tx,ty;
	for(int i=0;i<4;i++){
		tx=x+dir[i][0];
		ty=y+dir[i][1];
		if(tx>=0&&tx=0&&ty>n>>m;	
	sum=0;
	for(int i=0;i>s[i];
	} 
	for(int i=0;i

ov.
転載先:https://www.cnblogs.com/moyujiang/p/11167756.html