Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/tree_policy.hpp>
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pi;
- typedef pair<ll, ll> pl;
- typedef pair<ld, ld> pd;
- typedef vector<int> vi;
- typedef vector<ll> vl;
- typedef vector<ld> vd;
- typedef vector<pi> vpi;
- typedef vector<pl> vpl;
- template <class Key, class Compare = less<Key>> // find_by_order, order_of_key (for multiset: pair(val, time of insertion))
- using Tree = tree<Key, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;
- int R, C;
- int grid[24][24];
- map<int, int> dp[24][24];
- const int allon = (1 << 21) - 1;
- int dr[4] = {-1, 0, 1, 0};
- int dc[4] = {0, 1, 0, -1};
- inline bool in(int r, int c) {
- return r >= 1 && r <= R && c >= 1 && c <= C;
- }
- int dfs(int r, int c, int m) {
- if (m == allon) {
- return 1;
- } else if (dp[r][c].count(m) != 0) {
- return dp[r][c][m];
- } else {
- int res = 0;
- for (int d = 0; d < 4; ++d) {
- int r1 = r + dr[d], c1 = c + dc[d];
- if (in(r1, c1)) {
- int b = grid[r1][c1];
- if (b != -1 && (m & (1 << b)) == 0) {
- res += dfs(r1, c1, m | (1 << b));
- }
- }
- }
- return dp[r][c][m] = res;
- }
- }
- void _SOLVE_() {
- cin >> R >> C;
- memset(grid, -1, sizeof(grid));
- for (int r = 1; r <= R; ++r) {
- for (int c = 1; c <= C; ++c) {
- string s;
- cin >> s;
- if (s[0] != '_') {
- grid[r][c] = 10*(s[1] - '0') + (s[2] - '0') - 1;
- }
- }
- }
- int ans = 0;
- for (int r = 1; r <= R; ++r) {
- for (int c = 1; c <= C; ++c) {
- if (grid[r][c] != -1) {
- ans += dfs(r, c, 1 << grid[r][c]);
- }
- }
- }
- cout << ans << endl;
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- #ifdef _DEBUG
- freopen("in.txt", "r", stdin);
- freopen("out.txt", "w", stdout);
- #endif
- _SOLVE_();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement