【深捜し(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