為了做研究，源外老教授弄到了一台特殊的 DNA 掃描儀，這台機器可以把目前獲得的 DNA 們分離成一個個的小片段，之後拍張照片作為掃描結果，拿來分析與研究。
掃描結果會是高度為 H、寬度為 W 的矩形方格，每個方格可能有兩種狀態：「有 DNA」或「無 DNA」。在所獲得的結果中，如果兩個上、下、左，右相鄰的方格都滿足「有 DNA」，那麼稱作這兩格的 DNA 為聯通的。所有直接或間接聯通，且滿足「有DNA」的方格，則屬於同一個片段。如果兩個「有 DNA」的方格完全沒有連通，則屬於不同片段。換句話說，片段由許多直接或間接連通而「有 DNA」的一些方格所組成。
已知每個片段的長相只有「線形」與「環形」兩種可能。
「線形」的片段為一條鏈，也即可以在此片段中找到恰好一個起始方格，接著沿著唯一的方向，依序找尋下一個方格，直到遇到最後一個方格為止，且此方格與起始方格不會上、下、左，右相臨。保證在找尋方格的過程中不會遇到任何岔路，且此片段至少包含 2 格。
「環形」的片段為一個環，也即在此片段中，每個方格都可以視為起始方格，從起始方格出發，從恰兩個方向中任選一個前進，接著沿著唯一的方向，依序找尋下一個方格，直到遇到最後一個方格為止，此方格會與起始方格上、下、左，右相臨。保證在找尋方格的過程中不會遇到岔路，從起始方格出發必定恰有兩個可能的找尋方向，且此片段至少包含 8 格。
在這次的研究中，源外老頭不關心任何「線形」的片段，但想要好好分析「環形」的片段，由於這些資料太過於龐大了，你希望寫一支程式協助分析這些結果。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 輸入的第一列為兩個正整數 H 和 W，表示掃描結果為高度 H、寬度 W 的矩形方格。 接著共有 H 列，每列均恰有 W 個字元，其中字元「.」（不含引號）表示該格「有 DNA」，字元「#」（不含引號）表示該格「無 DNA」。除此之外，該列不會有其他的字元。 | 請輸出一列，其中包含三個正整數 X、Y、Z，並以一個空白隔開，表示總共有 X 個「環形」片段，這些片段長度的總和為 Y，乘積為 Z。保證至少有一個「環形」片段，且滿足 Z < 264。 |
| 3 3 … .#. … | 1 8 8 |
| 5 6 ###### …#.. .#.### …#.# ####.# | 1 8 8 |
| 11 7 ……. .#####. .#…#. .#.#.#. .#…#. .#####. ……. ####### #….#. ..##.#. .###… | 2 32 192 |
解題思路
使用 DFS，每次從主程式呼叫 DFS 的時候紀錄目前的陣列位置，當 DFS 走回起點的時後判斷走的步數是否 >= 4，如果 >= 4 的話就代表走了一圈，將走的步數存到一個陣列中。走 DFS 的時候優先判斷是否可以往下或右走，只要走了一步就 break 迴圈。
將答案陣列的長度輸出設定為 X，陣列中資料總和設定為 Y，陣列中所有資料的乘積設定為 Z。另外，因為乘積會很大所以需要使用 Unsigned Long Long Int。
範例程式碼－ZeroJudge B683: 環形偵測
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int H, W, loc[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<string>num;
vector<unsigned long long int>ans;
map<pair<int, int>, int>MAP;
pair<int, int> axis (int a, int b)
{
pair<int, int>tmp;
tmp.first = a;
tmp.second = b;
return tmp;
}
void DFS(pair<int, int>point, pair<int, int>start, unsigned long long int count)
{
MAP[point]++;
if (point == start && MAP[point] == 1 && count >= 4)
{
ans.push_back(count);
return;
}
for (int i = 0; i<4; i++)
{
int yy = point.first + loc[i][0], xx = point.second + loc[i][1];
if (yy >= 0 && yy < H && xx >= 0 && xx < W && num[yy][xx] == '.' && MAP[axis(yy, xx)] == 0)
{
DFS(axis(yy, xx), start, count+1);
return;
}
}
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> H >> W;
for (int i = 0; i<H; i++)
{
string str;
cin >> str;
num.push_back(str);
}
for (int i = 0; i<H; i++)
{
for (int j = 0; j<W; j++)
{
if (MAP[axis(i, j)] == 0 && num[i][j] == '.')
{
MAP[axis(i, j)]--;
DFS(axis(i, j), axis(i, j), 0);
}
}
}
cout << ans.size();
unsigned long long int Y = 0, Z = 1;
for (int i = 0; i<ans.size(); i++)
{
Y += ans[i];
Z *= ans[i];
}
cout << " " << Y << " " << Z << "\n";
}
//ZeroJudge B683
//Dr. SeanXD