Intermediate.
Put your skills to the test.

Problem summary

Number starts of horizontal and vertical crossword words in row-major order. Words contain at least two white cells. Report counts, lengths for a specified start number, and word numbers covering a specified cell.

Constraints

2 ≤ M,N ≤ 20; coordinates and word numbers are 1-based.

Worked example

Input and output for the worked example discussed below.

5 4
0 0 0 0
0 0 -1 -1
-1 0 -1 0
-1 0 0 0
0 0 0 0
3
1 3

4 4
2 0
1 0

Solution analysis

1. A horizontal word begins at a white cell whose left neighbour is absent or black and whose right neighbour is white. The successor condition excludes one-cell runs. Use the analogous up/down condition for vertical words.
2. Scan top to bottom, left to right. Assign the next number once when either condition holds, sharing it if both hold. Walk each new word to record its length and label its cells in an orientation-specific coverage array.
3. The sample has four horizontal and four vertical words. Number 3 begins a horizontal word of length 2 but no vertical word. Cell (1,3) belongs to horizontal word 1 and no vertical word. Separate coverage arrays make all three reports direct lookups.

Why it works

The start tests characterize exactly maximal white runs of length at least two. Row-major numbering matches the specified ordering, and the walks label exactly each word’s cells. Counts, lengths, and coverage lookups therefore answer their definitions.

Watch out. Number a shared start once. Single white cells are not words. Black cells and isolated cells can have zero coverage.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int rows;
    int columns;
    cin>>rows>>columns;
    vector<vector<int>>grid(rows+2,vector<int>(columns+2,-1));
    for(int r=1;r<=rows;r++){
        for(int c=1;c<=columns;c++){
            cin>>grid[r][c];
        }
    }
    vector<vector<int>>horizontal(rows+2,vector<int>(columns+2));
    vector<vector<int>>vertical=horizontal;
    vector<int>hLength(rows*columns+1);
    vector<int>vLength(rows*columns+1);
    int number=0;
    int hCount=0;
    int vCount=0;
    for(int r=1;r<=rows;r++){
        for(int c=1;c<=columns;c++){
            if(grid[r][c]!=0){
                continue;
            }
            bool across=grid[r][c-1]!=0&&grid[r][c+1]==0;
            bool down=grid[r-1][c]!=0&&grid[r+1][c]==0;
            if(!across&&!down){
                continue;
            }
            // A shared start receives one number, not one per orientation.
            number++;
            if(across){
                hCount++;
                for(int next=c;grid[r][next]==0;next++){
                    horizontal[r][next]=number;
                    hLength[number]++;
                }
            }
            if(down){
                vCount++;
                for(int next=r;grid[next][c]==0;next++){
                    vertical[next][c]=number;
                    vLength[number]++;
                }
            }
        }
    }
    int query;
    int r;
    int c;
    cin>>query>>r>>c;
    cout<<hCount<<' '<<vCount<<'\n';
    if(query<1||query>number){
        cout<<"0 0\n";
    }
    else{
        cout<<hLength[query]<<' '<<vLength[query]<<'\n';
    }
    cout<<horizontal[r][c]<<' '<<vertical[r][c]<<'\n';
}