2016年7月20日 星期三

DFS應用-1

           ,      No comments   
DFS應用-1： (A)有幾處水窪?上下左右算連通 (B)最大一處有多大{1個數數}?  (C,D)改成類似踩地雷(八方)算連通
0
1
2
3
4
5
6


0
1
2
3
4
5
6


0
1
2
3
4
5
6
7




0




1
1
1

0
1



1
1
1

0
1
1




1





1

1
1

1

1

1

1
1

1

1


0
1
2
3
4


0
1
2
3
4
2


1

1

1

2


1


1


0




1

0

1

1

3
1

1





3
1
1






1

1
1

1

1


1


4
1

1


1
1

4


1
1

1
1

2

1


1

2

1

1

5






1

5
1





1

3
1
1
1

1







6

1
1
1
1



6

1
1
1
1



4
1
1


1






































讀入資料：空白處以0代替
Vb版→
   in1.txt 第1列為2有兩組資料
in1.txt 第1列為2有兩組資料
輸入→

C++版：
右列5組合成一個輸入檔
第1列為5
7 7
0000111
0110101
0010101
1010000
1010011
0000001
0111100
7 7
1000111
0110101
0010010
1100000
0011011
1000001
0111100
1 8
110000010
5 5
00001
01101
01001
11101
11001
3 5
01001
00110
01001
(A)輸出
5
9
2
2
5
(B)輸出
7
5
2
8
2
(C)輸出
5
4
2
2
1
(D)輸出
7
8
2
5
6


四種程式，輸入資料一樣，不同的輸出，自己寫程式看看 下圖為(A)(B)的水窪處，紅色為最大窪
0
1
2
3
4
5
6


0
1
2
3
4
5
6


0
1
2
3
4
5
6
7




0




1
1
1

0
1



1
1
1

0
1
1




1





1

1
1

1

1

1

1
1

1

1


0
1
2
3
4


0
1
2
3
4
2


1

1

1

2


1


1


0




1

0

1


1
3
1

1





3
1
1






1

1
1

1

1


1
1

4
1

1


1
1

4


1
1

1
1

2

1


1

2

1


1
5






1

5
1





1

3
1
1
1

1







6

1
1
1
1



6

1
1
1
1



4
1
1


1






































下圖為(C)(D)的水窪處，紅色為最大窪
0
1
2
3
4
5
6


0
1
2
3
4
5
6


0
1
2
3
4
5
6
7




0




1
1
1

0
1



1
1
1

0
1
1




1





1

1
1

1

1

1

1
1

1

1


0
1
2
3
4


0
1
2
3
4
2


1

1

1

2


1


1


0




1

0

1


1
3
1

1





3
1
1






1

1
1

1

1


1
1

4
1

1


1
1

4


1
1

1
1

2

1


1

2

1


1
5






1

5
1





1

3
1
1
1

1







6

1
1
1
1



6

1
1
1
1



4
1
1


1








































0 意見:

張貼留言