Intermediate.
Put your skills to the test.

Problem summary

A robot moves between side-adjacent passable cells of a connected grid. It cannot immediately return to the cell it just left. Decide whether, from every starting cell, it can visit every desired cell and return to its start. Print 0 if this is always possible and 1 otherwise.

Constraints

3 ≤ M,N ≤ 20; at least two passable cells; passable cells form one connected component.

Worked example

The worked example illustrates the rule described in the analysis.

4 3
XXX
X.X
X.X
XXX

1

Solution analysis

1. View each passable cell as a vertex and each side adjacency as an undirected edge. Count its neighbours using four direction offsets and explicit bounds checks.
2. A degree-one cell is fatal: after entering it, the only next move would immediately reverse the preceding move. Therefore some required round trip is impossible.
3. Conversely, if every cell has at least two neighbours, one can extend a route until it reaches a cycle, traverse that cycle, and return along the approach without an immediate reversal. This allows turning around beyond a target. Bridges are allowed: cycles at both ends provide the necessary turnarounds.
4. In the example, the two free cells each have degree one, so the answer is 1. Two rings joined by a corridor can instead satisfy the condition; rejecting every bridge would be incorrect.

Why it works

Necessity follows from an endpoint with no legal onward move. For sufficiency, extend any simple route beyond its endpoint without reversing. In a finite graph with minimum degree two, the extension eventually meets a previously visited vertex and produces a cycle. Following that cycle permits reversing the approach legally. Applying this to routes between any chosen pair yields the required round trips.

Watch out. Do not reject bridges. Diagonal cells are not neighbours. Connectivity is a statement guarantee; minimum degree alone would not imply connectivity.

An independently written complete program with standard headers.

#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
int main(){
    int rows,columns;
    cin>>rows>>columns;
    vector<string>grid(rows);
    for(string&row:grid){
        cin>>row;
    }
    const int dr[]={-1,1,0,0};
    const int dc[]={0,0,-1,1};
    for(int r=0;r<rows;++r){
        for(int c=0;c<columns;++c){
            if(grid[r][c]!='.'){
                continue;
            }
            int degree=0;
            for(int direction=0;direction<4;++direction){
                int nr=r+dr[direction];
                int nc=c+dc[direction];
                if(nr>=0&&nr<rows&&nc>=0&&nc<columns&&grid[nr][nc]=='.'){
                    ++degree;
                }
            }
            // A leaf forces an immediate reversal after arrival.
            if(degree<2){
                cout<<1<<'\n';
                return 0;
            }
        }
    }
    cout<<0<<'\n';
}