ccbeginner

TIOJ 1908 (help me...)

Feb 15th, 2020
122
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //TIOJ 1908
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int arr[22][22];
  6. int vis[22];
  7. map<int, int> dp[22];
  8. int n;
  9.  
  10. int dx[] = {-1,-1,-1,0,0,1,1,1};
  11. int dy[] = {-1,0,1,-1,1,-1,0,1};
  12.  
  13. int dfs(int depth){
  14.     if(depth == n * n)return 0;
  15.     int x = depth / n;
  16.     int y = depth % n;
  17.     if(y == 0 && dp[x].find(vis[x]) != dp[x].end())return dp[x][vis[x]];
  18.     int ret = 0;
  19.     if(!(vis[x] & (1<<y))){
  20.         vector<int> take;
  21.         for(int i = 0 ; i < 8; ++i){
  22.             int nx = x + dx[i], ny = y + dy[i];
  23.             if(0 <= nx && nx < n && 0 <= ny && ny < n && !(vis[nx] & (1<<ny))){
  24.                 take.emplace_back(i);
  25.                 vis[nx] |= (1<<ny);
  26.             }
  27.         }
  28.         vis[x] |= (1<<y);
  29.         ret = dfs(depth+1) + arr[x][y];
  30.         for(unsigned i = 0; i < take.size(); ++i){
  31.             int nx = x + dx[take[i]], ny = y + dy[take[i]];
  32.             vis[nx] &= ~(1<<ny);
  33.         }
  34.         vis[x] &= ~(1<<y);
  35.     }
  36.     if(x < 2 || y < 2 || (vis[x-2]&(1<<(y-2))))ret = max(ret, dfs(depth+1));
  37.     if(y == 0)dp[x][vis[x]] = ret;
  38.     return ret;
  39. }
  40.  
  41. int32_t main(){
  42.     cin >> n;
  43.     for(int i = 0; i < n; ++i){
  44.         for(int j = 0; j < n; ++j){
  45.             cin >> arr[i][j];
  46.         }
  47.     }
  48.     cout << dfs(0) << '\n';
  49.     return 0;
  50. }
RAW Paste Data