Proficient.
Put your skills to the test.

Problem summary

Cats occupy distinct cells of a rectangular grid. Each cat can leave by reaching a boundary cell, moving through orthogonally adjacent cells, but may never enter a cell ever occupied by another cat. Maximize the number that escape.

Constraints

1≤N,M≤30.

Worked example

An independently prepared example for this explanation.

3
0001
0110
1010

5

Solution analysis

1. Escape routes must be vertex-disjoint. Split every cell into an in-vertex and an out-vertex joined by capacity 1, making at most one route use that cell.
2. Connect the source to each occupied cell’s in-vertex, and each boundary out-vertex to the sink. Add movement edges from a cell’s out-vertex to neighboring empty cells only. A cat may start at its own occupied cell, but another route may never pass through that cell, even if its original cat is not selected to escape.
3. The first sample has five cats, and each can escape, so the flow is 5. In the second official sample, the tighter 5×6 configuration permits fifteen of sixteen cats to escape. Paths to boundary cells already count as leaving; no extra outside movement is needed.

Why it works

Every successful collection of routes gives an integral flow: unit cell capacities enforce disjointness, and excluded entries into occupied cells preserve all original cat positions. Conversely an integral flow decomposes into source-to-boundary paths, after discarding cycles. These paths avoid one another and all other starting cats, so they can be followed safely. Maximum flow therefore equals the maximum escapes.

Watch out. Unselected cats still block their starting cells. Split vertices to enforce cell capacity, and connect every boundary cell including corners only once to the sink.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
// Algorithm: Escape routes must be vertex-disjoint.
using namespace std;
struct Edge{
    int to;
    int reverse;
    int capacity;
};
struct Dinic{
    vector<vector<Edge>>graph;
    vector<int>level;
    vector<int>nextEdge;
    explicit Dinic(int vertices):graph(vertices),level(vertices),nextEdge(vertices){
    }
    void addEdge(int from,int to,int capacity){
        Edge forward={to,static_cast<int>(graph[to].size()),capacity};
        Edge backward={from,static_cast<int>(graph[from].size()),0};
        graph[from].push_back(forward);
        graph[to].push_back(backward);
    }
    bool buildLevels(int source,int sink){
        fill(level.begin(),level.end(),-1);
        queue<int>pending;
        pending.push(source);
        level[source]=0;
        while(!pending.empty()){
            int vertex=pending.front();
            pending.pop();
            for(const Edge&edge:graph[vertex]){
                if(edge.capacity>0&&level[edge.to]==-1){
                    level[edge.to]=level[vertex]+1;
                    pending.push(edge.to);
                }
            }
        }
        return level[sink]!=-1;
    }
    int send(int vertex,int sink,int amount){
        if(vertex==sink){
            return amount;
        }
        for(int&index=nextEdge[vertex];index<static_cast<int>(graph[vertex].size());index++){
            Edge&edge=graph[vertex][index];
            if(edge.capacity>0&&level[edge.to]==level[vertex]+1){
                int sent=send(edge.to,sink,min(amount,edge.capacity));
                if(sent!=0){
                    edge.capacity-=sent;
                    graph[edge.to][edge.reverse].capacity+=sent;
                    return sent;
                }
            }
        }
        return 0;
    }
    int maximumFlow(int source,int sink){
        int total=0;
        while(buildLevels(source,sink)){
            fill(nextEdge.begin(),nextEdge.end(),0);
            int sent;
            while((sent=send(source,sink,1000000000))!=0){
                total+=sent;
            }
        }
        return total;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int rows;
    cin>>rows;
    vector<string>grid(rows);
    for(string&row:grid){
        cin>>row;
    }
    int columns=static_cast<int>(grid[0].size());
    int source=2*rows*columns;
    int sink=source+1;
    Dinic network(sink+1);
    const int dr[4]={-1,1,0,0};
    const int dc[4]={0,0,-1,1};
    for(int row=0;row<rows;row++){
        for(int column=0;column<columns;column++){
            int in=2*(row*columns+column);
            int outVertex=in+1;
            network.addEdge(in,outVertex,1);
            if(grid[row][column]=='1'){
                network.addEdge(source,in,1);
            }
            if(row==0||row==rows-1||column==0||column==columns-1){
                network.addEdge(outVertex,sink,1);
            }
            for(int direction=0;direction<4;direction++){
                int nr=row+dr[direction];
                int nc=column+dc[direction];
                if(nr>=0&&nr<rows&&nc>=0&&nc<columns&&grid[nr][nc]=='0'){
                    network.addEdge(outVertex,2*(nr*columns+nc),1);
                }
            }
        }
    }
    cout<<network.maximumFlow(source,sink)<<'\n';
}