Proficient.
Put your skills to the test.

Problem summary

On a grid with traps, players move a token to unused side-adjacent free cells, permanently trapping the cell they leave. The first move chooses any free cell. Choose whether to play first or second and implement the official grader dialogue to guarantee a win.

Constraints

1 ≤ N,M ≤ 100; # marks traps and . marks free cells.

Worked example

The official example is an illustrative dialogue, not a unique output. Matching choices can produce a different winning dialogue.

Official demonstration: empty 3×3 grid; moves begin at (1,1).

The demonstrated first player wins after five moves.

Solution analysis

1. The free-cell graph is bipartite by checkerboard color. Compute a maximum matching with Hopcroft–Karp. If every free vertex is matched, choose to play second. After each opponent move, move to its matched partner.
2. If an unmatched free vertex exists, choose first and start there, then again answer every opponent move with its matched partner. Such a partner is always unvisited: otherwise the played path would revisit a vertex, or there would be an alternating augmenting path from the unmatched start to another unmatched vertex, contradicting maximality of the matching.
3. An empty 3×3 board has an unmatched cell in any maximum matching, so the strategy chooses first and wins. The official example starts at the center; another unmatched starting cell with its matching response plan is equally valid. If the board has no free cells, choose second and receive the grader’s immediate surrender.

Why it works

With a perfect matching, pair responses use a fresh matching edge after each opponent move. A previously used partner would force a repeated vertex on the alternating played path, which legal moves prohibit. With an unmatched starting vertex, an opponent move to another unmatched vertex would create an augmenting path, impossible for a maximum matching; a matched partner is fresh by the same path argument. Thus whenever the opponent can move the strategy has a legal response, and the finite game ends with the opponent unable to move. Hopcroft–Karp supplies the required maximum matching.

Watch out. Preserve the zero-based grader coordinates and (−1,−1) handshake. Do not replace the interactive callback by a board solver that only prints a starting position. Return immediately on surrender.

Official hunter.h callback with no main. A separate local harness drives makeMove and validates every move; the callback is not a standard-input submission.

#include"hunter.h"
#include<functional>
#include<queue>
#include<utility>
#include<vector>
// Algorithm: The free-cell graph is bipartite by checkerboard color.
using namespace std;
void play(int n,int m,const vector<vector<char>>&table){
    int vertices=n*m;
    vector<vector<int>>adjacent(vertices);
    vector<int>left;
    const int dr[4]={-1,1,0,0};
    const int dc[4]={0,0,-1,1};
    for(int r=0;r<n;r++){
        for(int c=0;c<m;c++){
            if(table[r][c]!='.'||(r+c)%2){
                continue;
            }
            int u=r*m+c;
            left.push_back(u);
            for(int direction=0;direction<4;direction++){
                int nr=r+dr[direction];
                int nc=c+dc[direction];
                if(nr>=0&&nr<n&&nc>=0&&nc<m&&table[nr][nc]=='.'){
                    adjacent[u].push_back(nr*m+nc);
                }
            }
        }
    }
    vector<int>partner(vertices,-1),distance(vertices);
    while(true){
        queue<int>pending;
        for(int u:left){
            distance[u]=partner[u]==-1?0:-1;
            if(distance[u]==0){
                pending.push(u);
            }
        }
        int shortest=vertices+1;
        while(!pending.empty()){
            int u=pending.front();
            pending.pop();
            if(distance[u]>=shortest){
                continue;
            }
            for(int v:adjacent[u]){
                if(partner[v]==-1){
                    shortest=distance[u]+1;
                }
                else if(distance[partner[v]]==-1){
                    distance[partner[v]]=distance[u]+1;
                    pending.push(partner[v]);
                }
            }
        }
        if(shortest==vertices+1){
            break;
        }
        function<bool(int)>augment=[&](int u){
            for(int v:adjacent[u]){
                int next=partner[v];
                if((next==-1&&distance[u]+1==shortest)||
                    (next!=-1&&distance[next]==distance[u]+1&&augment(next))){
                    partner[u]=v;
                    partner[v]=u;
                    return true;
                }
            }
            distance[u]=-1;
            return false;
        };
        for(int u:left){
            if(partner[u]==-1){
                augment(u);
            }
        }
    }
    int start=-1;
    for(int u=0;u<vertices;u++){
        if(table[u/m][u%m]=='.'&&partner[u]==-1){
            start=u;
            break;
        }
    }
    pair<int,int>opponent=start==-1?makeMove(-1,-1):makeMove(start/m,start%m);
    while(opponent.first!=-1){
        int response=partner[opponent.first*m+opponent.second];
        opponent=makeMove(response/m,response%m);
    }
}