Problem: Example

Input

0 3 1 7 5 9 8 6 4 2
7 0 9 2 1 5 4 8 6 3
4 2 0 6 8 7 1 3 5 9
1 7 5 0 9 8 3 4 2 6
6 1 2 3 0 4 5 9 7 8
3 6 7 4 2 0 9 5 8 1
5 8 6 9 7 2 0 1 3 4
8 9 4 5 3 6 2 0 1 7
9 4 3 8 6 1 7 2 0 5
2 5 8 1 4 3 6 7 9 0


Output

0

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

map<string,int> memo;

void write_memo(vector<string>& ids, vector< vector<int> >& tab) {
	for (int i = 0; i < ids.size(); ++i) {
		int row = 0;
		int col = 0;
		for (int j = 0; j < ids[i].length(); ++j) {
			col = ids[i][j] - '0';
			row = tab[row][col];
		}
		memo[ids[i]] = row;
	}
}

bool check_ssn(string id, vector< vector<int> >& tab) {
	int base = memo[id];
	for (int i = 0; i < id.length(); ++i) {
		for (int j = '0'; j <= '9'; ++j) {
			string temp = id;
			if ((char)j != temp[i]) {
				temp[i] = j;
				if (tab[memo[temp]][base] == 0) {
					return false;
				}
			}
		}
	}

	for (int i = 0; i < 10; ++i) {
		if (i != base) {
			if (tab[base][i] == 0) {
				return false;
			}
		}
	}

	for (int i = 0; i < id.length()-1; ++i) {
		string temp = id;
		if (temp[i] != temp[i+1]) {
			char c = temp[i];
			temp[i] = temp[i+1];
			temp[i+1] = c;
			if (tab[memo[temp]][base] == 0) {
				return false;
			}
		}
	}

	string temp = id;
	if (temp[3] != base + '0') {
		temp[3] = base + '0';
		if (tab[memo[temp]][id[3]-'0'] == 0) {
			return false;
		}
	}

	return true;
}

int main(void) {
	vector< vector<int> > tab(10,vector<int>(10));
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10; ++j) {
			cin >> tab[i][j];
		}
	}

	vector<string> ids;
	for (int i = 0; i < 10000; ++i) {
		string str = to_string(i);
		int ml = 4 - str.length();
		string temp = "";
		for (int j = 0; j < ml; ++j) {
			temp += "0";
		}
		ids.push_back(temp+str);
	}
	write_memo(ids,tab);

	int res = 0;
	for (int i = 0; i < ids.size(); ++i) {
		if (!check_ssn(ids[i],tab)) {
			++res;
		}
	}
	cout << res << endl;
	return 0;
}