hihocoder 1310 島嶼

2022-11-24 16:26:30 字數 2662 閱讀 6482

時間限制:10000ms

單點時限:1000ms

記憶體限制:256mb

給你一張某一海域衛星**,你需要統計:

1. **中海島的數目

2. **中面積不同的海島數目

3. **中形狀不同的海盜數目

其中海域的**如下,"."表示海洋,"#"表示陸地。在"上下左右"四個方向上連在一起的一片陸地組成一座島嶼。

.####..  

.....#.

####.#.

.....#.

..##.#.

上圖所示的**中一共有4座島嶼;其中3座面積為4,一座面積為2,所以不同面積的島嶼數目是2;有兩座形狀都是"####",所以形狀不同的島嶼數目為3。

第一行包含兩個人整數:n 和 m,(1 ≤ n, m ≤ 50),表示**的行數和列數。

以下一個 n * m 的矩陣,表示表示海域的**。

輸出3個整數,依次是**中海島的數目、面積不同的海島數目和形狀不同的海島數目。

樣例輸入

5 7

. # # # # . .

. . . . . # .

# # # # . # .

. . . . . # .

. . # # . # .

樣例輸出

4 2 3

思路:(1)求島嶼數目很簡單,初始化島嶼數目numofislands為0,遍歷所有的點,如果這個點未訪問並且為‘#’,則numofislands++,進行dfs搜尋,將和這個點屬於同一個島嶼的所有為'#'的點標記為已訪問。

(2)求解一個島嶼時,計算它的面積,將所有的面積儲存下來,去掉重複元素,剩下元素個數即為面積不同的島嶼數。

(3)dfs搜尋出所有島嶼,同時把每個島嶼包含的畫素座標也儲存起來並按照座標排序(先根據x從小到大排序,如果x座標相同,再根據y從小到大排序)。  形狀相同的島嶼數目我們可以通過逐一比較島嶼的每一個畫素得到。當我們比較島嶼x和島嶼y時,如果每對畫素的座標差都相同,那麼x和y的形狀就是相同的。(首先如果兩個島嶼的面積數不同,形狀肯定不同,再根據島嶼x的第i(1 <= i <= 面積-1)個座標與其第一個座標的座標差?=島嶼y的第i個座標與其第一個座標的座標差,如果有一個不相等,則形狀不同)。

1 #include 2 #include 3 #include 

4 #include 5 #include 6

using

namespace

std;78

int n, m;//

n為行數,m為列數

9char map[55][55];//

儲存字元矩陣

10bool visit[55][55];//

作為標記的陣列

1112

int dx[4] = ;//

方向陣列,為了優化dfs**

13int dy[4] = ;

14int area = 0;15

16int numofislands = 0, nodai = 0, nodci;//

最終numofislands表示島嶼數,nodai表示不同面積的島嶼數,

17//

計算過程中numofislands也作為某個島嶼的編號,島嶼編號從0開始

1819

struct

position ;

2324

int num[300];//

num[i]儲存了編號i島嶼的面積大小

2526

struct position a[300][300];//

表示最多有300個島嶼,每個島嶼最大面積為300即對應300個座標

2728

29bool flag[300

];30

31bool cmp(struct position a, struct

position b)

3738

int issame(struct position *c, struct position *d, int x, int y)49}

50return

flag;51}

5253

void dfs(int x, int

y)64}65

66int

main()85}

86}8788 nodai = v.size();//

面積不同的島嶼數

8990 nodci =numofislands;

9192

//對每個島嶼的座標進行排序,方便比較兩個島嶼形狀是否相同

93for(i = 0; i < numofislands; i++)

9697

//計算形狀不同的島嶼數

98for(i = 0; i < numofislands - 1; i++)

102else

108}

109}

110111

}112

113 cout << numofislands << "

"<< nodai << "

"<< nodci <114//

system("pause");

115return0;

116 }

1310 N皇后問題

今天在北航oj上看到這道n皇后問題,記得做八皇后問題還是在大一c語言課上學的,當時還沒接觸演算法,自然不懂回溯和遞迴,所以對八皇后的解法也只是理解了個大概,今天做到這題,上網搜了一下具體的做法,搜到一篇講解很詳細的blog 看明白後也就覺得不難寫了,要做的就是演算法的優化。自己寫了非遞迴和遞迴的程式...

hihocoder 1014

題意是去字尾是輸入字串s的的個數。首先用結構體做,結構體更實現,而且通俗易懂些。一直建立數,每次建立都往子節點加1,查詢的時候找到最後那個字母時,輸出它的子節點的數字就可以了。1 include 2 include 3 include 4using namespace std 5struct nod...

hihoCoder 27

a qvqb 題目 分析 dfs序 棧 數學 可以發現,對於每組詢問,樹上是有很多點都只能等於0的 對於每個節點求出dfs序得到進來的時間和出去的時間 對於詢問的限制,可以用括號序列表示 然後根據各種情況討論結果 唯一需要計算的是兩顆子樹,大小分別為n,m,求c n,0 c m,0 c n,1 c ...