Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- #include <string>
- using namespace std;
- const int n = 7;
- const int len = n * n - 1;
- struct Move
- {
- int dr;
- int dc;
- char letter;
- };
- const vector<Move> moves = {
- {-1, 0, 'U'},
- {1, 0, 'D'},
- {0, -1, 'L'},
- {0, 1, 'R'}
- };
- string form;
- string res;
- int ans = 0;
- vector<vector<bool>> used(n + 2);
- vector<vector<int>> used_neighbours(n + 2);
- bool check() {
- for (int i = 0; i < len; ++i) {
- if (form[i] != '?' && form[i] != res[i]) {
- return false;
- }
- }
- return true;
- }
- void rec(int idx, int r, int c) {
- if (used[r][c]) {
- return;
- }
- if (idx < len && r == n && c == 1) {
- return;
- }
- if (idx == len) {
- if (r == n && c == 1) {
- if (check()) {
- ++ans;
- }
- }
- return;
- }
- int dr, dc;
- int bad_counter = 0;
- int i, j;
- for (i = 0; i < 4; ++i) {
- int dr = moves[i].dr;
- int dc = moves[i].dc;
- if ((r+dr == 1 && c+dc == 1) || (r+dr == n && c+dc == 1)) {
- continue;
- }
- if (r+dr == 0 || r+dr == n + 1 || c+dc == 0 || c+dc == n + 1) {
- continue;
- }
- if (!used[r+dr][c+dc] && used_neighbours[r+dr][c+dc] >= 2) {
- if (bad_counter == 1) {
- return;
- } else {
- bad_counter++;
- j = i;
- }
- }
- }
- for (const Move& it : moves) {
- dr = it.dr;
- dc = it.dc;
- used_neighbours[r+dr][c+dc]++;
- }
- if (bad_counter == 1) {
- used[r][c] = true;
- dr = moves[j].dr;
- dc = moves[j].dc;
- res[idx] = moves[j].letter;
- rec(idx + 1, r+dr, c+dc);
- used[r][c] = false;
- for (const Move& it : moves) {
- dr = it.dr;
- dc = it.dc;
- used_neighbours[r+dr][c+dc]--;
- }
- return;
- }
- used[r][c] = true;
- for (const Move& it : moves) {
- dr = it.dr;
- dc = it.dc;
- res[idx] = it.letter;
- rec(idx + 1, r+dr, c+dc);
- }
- used[r][c] = false;
- for (const Move& it : moves) {
- dr = it.dr;
- dc = it.dc;
- used_neighbours[r+dr][c+dc]--;
- }
- }
- int main() {
- cin >> form;
- res.resize(len);
- for (auto& x : used) {
- x.resize(n + 2, false);
- }
- for (auto& x : used_neighbours) {
- x.resize(n + 2, 0);
- }
- for (int i = 0; i < n + 2; ++i) {
- used[i][0] = true;
- used[0][i] = true;
- used[i][n + 1] = true;
- used[n + 1][i] = true;
- }
- for (int i = 1; i <= n; ++i) {
- used_neighbours[i][1]++;
- used_neighbours[1][i]++;
- used_neighbours[i][n]++;
- used_neighbours[n][i]++;
- }
- rec(0, 1, 1);
- cout << ans;
- return 0;
- }
Add Comment
Please, Sign In to add comment