Ноль в каждой строке и каждом столбце

Вобщем, если воспользоваться алгоритмом Куна поиска максимального паросочетания, и проверять его на равенство размеру матрицы, то - вот так, в лоб (честно говоря, писать красиво и эффектно просто жаль времени...) получается что-то вроде (проверку на квадратность входных матриц не делаю!!):

#include <vector>
#include <iostream>
#include <iomanip>
using namespace std;
vector<vector<int>> p1 = { {0,4,2,2},{6,0,0,4},{0,0,6,4},{8,4,0,0}};
vector<vector<int>> p2 = { {0,6,4,4},{4,0,0,4},{0,2,8,6},{6,4,0,0}};
vector<vector<int>> bipartee(const vector<vector<int>>& q)
{
    vector<vector<int>> p;
    for(size_t r = 0; r < q.size(); ++r)
    {
        p.push_back(vector<int>());
        for(size_t c = 0; c < q.size(); ++c)
            if (q[r][c] == 0) p[r].push_back(c);
    }
    return p;
}
bool try_kuhn(int v, vector<vector<int>>& g, vector<int>& mt, vector<bool>& used)
{
    if (used[v])  return false;
    used[v] = true;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (mt[to] == -1 || try_kuhn(mt[to],g,mt,used))
        {
            mt[to] = v;
            return true;
        }
    }
    return false;
}
bool check(const vector<vector<int>>& p)
{
    int n = p.size();
    vector<vector<int>> g = bipartee(p);
    vector<int> mt;
    vector<bool> used;
    mt.assign(n, -1);
    for(int v = 0; v < n; ++v) {
        used.assign(n,false);
        try_kuhn(v,g,mt,used);
    }
    int sum = 0;
    for (int i=0; i<n; ++i)
        if (mt[i] != -1) ++sum;
    if (sum == n)
    {
        for (int i=0; i<n; ++i)
            if (mt[i] != -1)
                cout << "(" << i << "," << mt[i] << ") ";
        cout << endl;
    }
    return (sum == n);
}

int main()
{
    cout << "First matrix: "  << check(p1) << endl;
    cout << "Second matrix: " << check(p2) << endl;
}

См. http://ideone.com/Kbhydg

Раз такая сложность в восприятии... Второй вариант - ветвей и отсечений. Покороче, но в эффективности не уверен...

vector<vector<int>> p1 = { {0, 4, 2, 2}, {6, 0, 0, 4}, {0, 0, 6, 4}, {8, 4, 0, 0}};
vector<vector<int>> p2 = { {0, 6, 4, 4}, {4, 0, 0, 4}, {0, 2, 8, 6}, {6, 4, 0, 0}};
bool check(const vector<vector<int>>& p, int r = 0)
{
    int n = p.size();
    static vector<bool> u;
    if (r == n) return true;
    if (r == 0) u = vector<bool>(n,false);
    for(int c = 0; c < n; ++c)
    {
        if (p[r][c] || u[c]) continue;
        u[c] = true;
        if (check(p,r+1))
        {
            cout << "(" << r << "," << c << ") ";
            if (r == 0) cout << endl;
            return true;
        }
        u[c] = false;
    }
    return false;
}
int main()
{
    cout << "First matrix: "  << check(p1) << endl;
    cout << "Second matrix: " << check(p2) << endl;
}

Написал решение в лоб. Ему не хватает ещё пары проверок, но думаю сойдет.

#include <iostream>
#include <vector>
using namespace std;
typedef  vector<vector<int>> matrix;
bool check(const matrix m) {
    // проверим матрицу
    if (m.size() == 0 || m[0].size() == 0) return false;
    // первый проход
    for (int i = 0; i < m.size(); i++) {
        int count = 0;
        for (int j = 0; j < m[i].size(); j++) {
            if (m[i][j] == 0) count++;
        }
        if (count != 1) return false;
    }
    for (int i = 0; i < m[0].size(); i++) {
        int count = 0;
        for (int j = 0; j < m.size(); j++) {
            if (m[j][i] == 0) count++;
        }
        if (count != 1) return false;
    }
    return true;    
}
int main() {
    matrix p1 = { {0,4,2,2},{6,0,0,4},{0,0,6,4},{8,4,0,0}};
    matrix p2 = { {0,6,4,4},{4,0,3,4},{0,2,8,6},{6,4,5,0}};
    matrix p3 = { {0,6,4,4},{4,3,0,4},{1,0,8,6},{6,4,6,0}};
    cout << "p1 = " << check(p1) << endl;
    cout << "p2 = " << check(p2) << endl;
    cout << "p3 = " << check(p3) << endl;
    return 0;
}