c++ dfs


  • 0
    class Solution {
     public:
      void dfs(vector<vector<string>>& res, vector<string>& cur, int level, int N) {
        if (level == N) res.push_back(cur);
        for (int i = 0; i < N; i++) {
          int lev = level;
          bool posValid = true;
    
          while (--lev >= 0) {
            int upleft = i - (level - lev), upright = i + (level - lev);
    
            if (cur[lev][i] == 'Q' || (upleft >= 0 && cur[lev][upleft] == 'Q') ||
                (upright < N && cur[lev][upright] == 'Q')) {
              posValid = false;
              break;
            }
          }
    
          if (!posValid) continue;  // current position invalid
    
          cur[level][i] = 'Q';
          dfs(res, cur, level + 1, N);
          cur[level][i] = '.';
        }
      }
    
      vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> cur(n, string(n, '.'));
        dfs(res, cur, 0, n);
        return res;
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.