UVa 11745 - Slitherlin

// UVa 11745 - Slitherlin

#include <iostream>
#include <string>
#include <string.h>
using namespace std;

int move[4][2] = { { 0, -1 }, { 0, 1 }, { 1, 0 }, { -1, 0 } };
int cc, r, c;
string board[101];
bool yet[101][101];

void dfs(int i, int j) {
	cc++;
	yet[i][j] = false;
	for (int k = 0; k < 4; k++) {
		int a = i + move[k][0];
		int b = j + move[k][1];
		if (a >= 0 && a <= 2 * r && b >= 0 && b <= 2 * c && (board[a][b] == '|' || board[a][b] == '-')) {
			a += move[k][0];
			b += move[k][1];
			if (yet[a][b])
				dfs(a, b);
		}
	}

}

int main() {
	int t;
	for (cin >> t; t; t--) {
		cin >> r >> c;
		getline(cin, board[0]);
		for (int i = 0; i <= 2 * r; i++)
			getline(cin, board[i]);
		bool invalid = false;
		// check numbers
		for (int i = 1; i <= 2 * r; i += 2)
			for (int j = 1; j <= 2 * c; j += 2) {
				if (board[i][j] >= '0' && board[i][j] <= '9') {
					// count adjacent
					int adjacent = 0;
					for (int k = 0; k < 4; k++) {
						int a = i + move[k][0];
						int b = j + move[k][1];
						if (a >= 0 && a <= 2 * r && b >= 0 && b <= 2 * c && (board[a][b] == '|' || board[a][b] == '-'))
							adjacent++;
					}
					// check validity
					if (board[i][j] - '0' != adjacent)
						invalid = true;
				}
			}
		// check degrees are 2
		for (int i = 0; i <= 2 * r; i += 2)
			for (int j = 0; j <= 2 * c; j += 2)
				if (board[i][j] == '+') {
					// count adjacent
					int adjacent = 0;
					for (int k = 0; k < 4; k++) {
						int a = i + move[k][0];
						int b = j + move[k][1];
						if (a >= 0 && a <= 2 * r && b >= 0 && b <= 2 * c && (board[a][b] == '|' || board[a][b] == '-'))
							adjacent++;
					}
					// check validity
					if (2 != adjacent && adjacent != 0)
						invalid = true;
				}
		// count edges
		int total_edges = 0;
		for (int i = 0; i <= 2 * r; i++)
			for (int j = 0; j <= 2 * c; j++)
				if (board[i][j] == '|' || board[i][j] == '-')
					total_edges++;
		// check single loop
		for (int i = 0; i <= 2 * r; i += 2)
			for (int j = 0; j <= 2 * c; j += 2)
				if (board[i][j] == '+' && (i < 2 * r && board[i + 1][j] == '|' || j < 2 * c && board[i][j + 1] == '-')) {
					cc = 0;
					memset(yet, true, sizeof(yet));
					dfs(i, j);
					if (cc != total_edges)
						invalid = true;
					break;
				}
		// output
		if (invalid)
			cout << "Invalid" << endl;
		else
			cout << "Valid" << endl;
	}
	return 0;
}