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

When using DFS, each time it's called from the main program, record the current array position. When DFS returns to the starting point, check if the number of steps taken is greater than or equal to 4. If it's greater than or equal to 4, it means a full cycle has been completed, and stores the number of steps taken in an array. During DFS traversal, prioritize checking if downward or rightward movement is possible. As soon as one step is taken, break the loop.

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