Kortit II

#include <bits/stdc++.h>
#include <vector>
using namespace std;

int extra = 0;

int char_to_int(char in) {
	return (int)in - 65;
}

int recursev(int n, int x, int dx, int y, int dy, vector<string> &field, vector<int> species, vector<vector<bool>> &used) {
	int out = 0;
	
	if (y == n - 1) {
		return 0;
	}
	
	if (used[y+1][dy-1]) {
		used[y+1][dy-1] = false;
		bool up = true;
		vector<int> new_species = species;
		for (int i = x; i <= x+dx; i++) {
			if (new_species[char_to_int(field[y][i])] != 1) {
				new_species[char_to_int(field[y][i])]--;
			} else {
				up = false;
				break;
			}
		}
		if (up) {
			out++;
			out += recursev(n, x, dx, y+1, dy-1, field, new_species, used);
		}
	}
	
	if (used[y][dy-1]) {
		used[y][dy-1] = false;
		bool down = true;
		vector<int> new_species = species;
		for (int i = x; i <= x+dx; i++) {
			if (new_species[char_to_int(field[y+dy][i])] != 1) {
				new_species[char_to_int(field[y+dy][i])]--;
			} else {
				down = false;
				break;
			}
		}
		if (down) {
			out++;
			out += recursev(n, x, dx, y, dy-1, field, new_species, used);
		}
	}
	
	return out;
}

int vertical(int n, int x, int dx, vector<string> &field, vector<int> species) {
	vector<vector<bool>> used(n);
	vector<bool> temp(n);
	fill(temp.begin(), temp.end(), true);
	fill(used.begin(), used.end(), temp);
	return recursev(n, x, dx, 0, n-1, field, species, used)+1;
}

int recurseh(int n, int x, int dx, vector<string> &field, vector<int> species, vector<vector<bool>> &used) {
	int out = 0;
	bool called = false;
	
	if (x == n - 1) {
		extra += vertical(n, x, dx, field, species);
		return -1;
	}
	
	
	if (used[x+1][dx-1]) {
		used[x+1][dx-1] = false;
		bool left = true;
		vector<int> new_species = species;
		for (int i = 0; i < n; i++) {
			if (new_species[char_to_int(field[i][x])] != 1) {
				new_species[char_to_int(field[i][x])]--;
			} else {
				left = false;
				break;
			}
		}
		if (left) {
			called = true;
			out++;
			out += recurseh(n, x+1, dx-1, field, new_species, used);
		}
	}
	
	if (used[x][dx-1]) {
		used[x][dx-1] = false;
		bool right = true;
		vector<int> new_species = species;
		for (int i = 0; i < n; i++) {
			if (new_species[char_to_int(field[i][x+dx])] != 1) {
				new_species[char_to_int(field[i][x+dx])]--;
			} else {
				right = false;
				break;
			}
		}
		if (right) {
			called = true;
			out++;
			out += recurseh(n, x, dx-1, field, new_species, used);
		}
	}
	
	if (!called) {
		extra += vertical(n, x, dx, field, species);
		out--;
	}
	return out;
}

int main() {
	int n;
	cin >> n;
	vector<string> field(n);
	vector<int> species(26);
	for (int i = 0; i < n; i++) {
		cin >> field[i];
	}
	for (auto i : field) {
		for (auto j : i) {
			species[char_to_int(j)]++;
		}
	}
	vector<vector<bool>> used(n);
	vector<bool> temp(n);
	fill(temp.begin(), temp.end(), true);
	fill(used.begin(), used.end(), temp);
	int h = recurseh(n, 0, n-1, field, species, used)+1;
	fill(temp.begin(), temp.end(), true);
	fill(used.begin(), used.end(), temp);
	int v = recursev(n, 0, n-1, 0, n-1, field, species, used)+1;
	//cout << h << endl << v << endl << extra << endl;
	cout << h*v+extra << "\n";
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 2

Group: 2, 3, 4, 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 3

Group: 3, 4, 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 4

Group: 4, 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 5

Group: 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 6

Group: 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc