Chemistry

#include <iostream>
#include <vector>
using namespace std;

long maxFlow = 0, startSum = 0, targetSum = 0;

class Graph;
class Edge;
int valence(char atom);
int findBackEdge(Graph *G, Edge edge);

class Edge {
public:
    int from;
    int to;
    int flow;

    Edge(int from=-1, int to=-1, int flow=0);
};

class Graph {

public:
    int v_num;
    int height;
    int width;
    vector<bool> checked;
    vector<vector<Edge> > edge;

    Graph(int height, int width);
    void addEdge(int from, int to, int flow);
    void init(int height, int width);
    void uncheckAll();
    int toVertNum(int i, int j);
};

Graph::Graph(int height, int width) {
    this->height = height;
    this->width = width;
    this->v_num = height * width + 2;
    checked.resize(v_num, false);
    edge.resize(v_num);
}

int findBackEdge(Graph *G, Edge edge) {
    for(int child = 0; child < G->edge[edge.to].size(); ++child)
        if(G->edge[edge.to][child].to == edge.from) {
            return child;
        }
    return -1;
}

int valence(char atom) {
    switch(atom) {
        case('H'):
            return 1;
        case('O'):
            return 2;
        case('N'):
            return 3;
        case('C'):
            return 4;
    }
    return 0;
}

void Graph::addEdge(int from, int to, int flow = 1) {
    edge[from].push_back(
            Edge(from, to, flow)
        );
}

void Graph::uncheckAll() {
    for(int i=0; i < v_num; ++i)
        checked[i] = false;
}

int Graph::toVertNum(int i, int j) {
    return i * width + j + 1;
}

void Graph::init(int height, int width) {
    for (int i = 0; i < height; i++)
        for (int j = 0; j < width; j++) {
            char atom;
            cin >> atom;
            if ( (i%2 + j%2)%2 == 0 ) {
                addEdge(0, toVertNum(i,j), valence(atom));
                startSum += valence(atom);
                if (i + 1 < height)
                    addEdge (toVertNum(i,j), toVertNum(i+1,j));
                if (j + 1 < width)
                    addEdge (toVertNum(i,j), toVertNum(i,j+1));
                if (i - 1 >= 0)
                    addEdge (toVertNum(i,j), toVertNum(i-1,j));
                if (j - 1 >= 0)
                    addEdge (toVertNum(i,j), toVertNum(i,j-1));
            }
            else {
                addEdge(toVertNum(i,j), v_num - 1, valence(atom));
                targetSum += valence(atom);
            }
        }
}

Edge::Edge(int from, int to, int flow) {
    this->from = from;
    this->to = to;
    this->flow = flow;
}

int tryPushFlow(Graph *G, int current = 0, int capacity = 5) {
    G->checked[current] = true;
    if(current == G->v_num-1) {
        maxFlow += capacity;
        return capacity;
    }
    for(int e=0; e < G->edge[current].size(); ++e) {
        Edge edge = G->edge[current][e];

        if(G->checked[edge.to] || edge.flow == 0)
            continue;

        int minCapacity = tryPushFlow(G, edge.to, min(edge.flow, capacity));
        if(minCapacity > 0) {
            G->edge[current][e].flow -= minCapacity;
            int backEdgeNum = findBackEdge(G, edge);
            if (backEdgeNum != -1)
                G->edge[edge.to][backEdgeNum].flow += minCapacity;
            else
                G->edge[edge.to].push_back(Edge(edge.to, current, minCapacity));
            return minCapacity;
        }
    }
    return 0;
}

int main() {
    int height, width;
    cin >> height >> width;
    Graph G = Graph(height, width);
    G.init(height, width);

    while(tryPushFlow(&G))
        G.uncheckAll();

    (maxFlow == startSum) && (maxFlow == targetSum) && (maxFlow != 0) ?
    cout << "Valid" : cout << "Invalid";
}