ZeroJudge B683: Ring Detection

For research purposes, Professor Sengai obtained a special DNA scanner. This machine can separate the obtained DNA into individual fragments, which are then photographed for scanning results to be analyzed and studied.

The scanning result will be a rectangular grid with height H and width W. Each grid can have two states: "DNA present" or "DNA absent". In the obtained results, if two adjacent squares up, down, left, and right all meet the "DNA present" condition, then the DNA of these two squares is called connected. All squares that are directly or indirectly connected and meet the "DNA present" condition belong to the same segment. If two "DNA present" squares are not connected at all, then they belong to different segments. In other words, a segment consists of several squares that are directly or indirectly connected and have "DNA present".

It is known that each segment can only be either "linear" or "circular" in shape.

A "linear" segment is a chain, meaning that within this segment, you can find exactly one starting square and then follow a unique direction, sequentially finding the next square until you reach the last square. The last square will not be adjacent to the starting square (neither up, down, left, nor right). It is guaranteed that during the search for squares, there will be no forks, and this segment contains at least 2 squares.

A "circular" segment is a loop, meaning that within this segment, each square can be considered the starting square. Starting from the starting square, you can choose to move in one of exactly two directions, and then follow a unique direction, sequentially finding the next square until you reach the last square. This last square will be adjacent to the starting square (either up, down, left, or right). It is guaranteed that during the search for squares, there will be no forks, and starting from the initial square, there will always be exactly two possible directions to search. Moreover, this segment contains at least 8 squares.

In this research, Professor Sengai is not concerned with any "linear" segments but wants to thoroughly analyze "circular" segments. Due to the overwhelming amount of data, you hope to write a program to assist in analyzing these results.

Sample Inputs/Outputs

Thought Process

使用 DFS，每次從主程式呼叫 DFS 的時候紀錄目前的陣列位置，當 DFS 走回起點的時後判斷走的步數是否 >= 4，如果 >= 4 的話就代表走了一圈，將走的步數存到一個陣列中。走 DFS 的時候優先判斷是否可以往下或右走，只要走了一步就 break 迴圈。

Set the length of the answer array as X, the sum of the data in the array as Y, and the product of all data in the array as Z. Additionally, since the product can be very large, Unsigned Long Long Int needs to be used.

Sample Code－ZeroJudge B683: Ring Detection

#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