• N皇后问题

定义： n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

1.八皇后问题：

细节：

• 皇后和象棋中的<王>或者<士>类似，可以走直线或者对角。不同之处在于，<王>每步只能走一个单位，而皇后可以走任意长度。

代码：

DFS：

• 根据上一点，可知，在放好k行皇后，准备放入k+1个皇后时，要与前k个分别检测是否冲突。
• 回溯：冲突检测为false时，DFS函数回立即返回，这可以看作是一种剪枝优化。

int chessBoard[n];
int count=0;

void dfs(int i,int n){
    if(i==n&&CheckValid()) { count++;return; }
    chessBoard[i]=j;
    for(int j=0;j<n;j++){
      if(CheckValid( j)){
        dfs(i+1);
      }
    }
 }

bool CheckValid(int j){
  for(int i=0;i<j;i++){
    if(chessBoard[i]==chessBoard[j]||
       chessBoard[i]-chessBoard[j]==i-j||
       chessBoard[i]-chessBoard[j]=j-i){
             return false; 
    }
  }
    return true;
}

int main(){
  int n=0;
  cin>>n;
  Queen(0,8);
  cout<<count;
}

一道和八皇后一样需要判断四个方向的问题：

LeetCode #54 螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

思路：
代码：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> >& matrix) {
        int len1=matrix.size(),len2=matrix[0].size();
        int left=0,right=len2-1,up=0,down=len1-1;
        int x=0,y=0,cur=0;
        int count=0;
        vector <int> order(len1*len2,0);
        while(count<len1*len2){
            order[count++]=matrix(x,y);
            if(x==right&&cur==0){
                up--;
                cur=1;
            }
            else if(y==down&&cur==1){
                right--;
                cur=2;
            }
            else if(x==left&&cur==2){
                down++;
                cur=3;
            }
            else if(y=up&&cur==3){
                left++;
                cur=1;
            }
            UpdatePos(&x,&y,cur);
        }
    }
private:
    void UpdatePos(int &x,int &y,int cur){
        vector<vector<int>> dir={{1,0},{0,1},{-1,0},{0,-1}};//四种方向 右 下 左 上
        x+=dir[cur][0];
        y+=dir[cur][1];
    }
};

• DFS问题

1. 美团0312面试题3：

m道菜，n个客人，每个客人要两道菜，求最多可以满足多少客人。
tips :用局部变量count和全局变量ans在递归中更新最大值。

vector<bool>menu(m,true);
vector<int>guest(n,1);
int ans=0;
void DFS(int i，int count){
  if(i==n){
    ans==max(ans,count);
    return;
  }
  if(menu[guest[i][0]]&&(menu[guest[i][1]]) { 
      menu[guest[i][0]]=false;
      menu[guest[i][1]]=false;
      DFS(i+1,count+1); 
  }
  DFS(i+1,count);
}

2. 最大岛屿问题

class Solution {
public:
    int maxAreaIsland(vector<vector<int> >& grid) {
        // write code here
        int ans=0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                ans=max(ans,DFS(i,j,grid));
            }
        }
        return ans;
    }
private:
    int DFS(int i,int j,vector<vector<int> >& grid){
        if(grid[i][j]==0){return 0;}
        if(i==grid.size-1()&&j==grid[i].size()-1){return 1; }
        else if(i=grid.size()-1) { return DFS(i,j+1,grid)+1; }
        else if(j=grid[0].size()-1) { return DFS(i+1,j,grid)+1; }
        else{
            return DFS(i,j+1,grid)+DFS(i+1,j,grid)+1;
        }
    }
};

优化：边缘处理：

if(x<0||y<0||x>=grid.size()||y>grid[0].size()){
    return 0;
}

然后可以不判断边缘直接四个方向DFS：

return 1+dfs(i+1,j)+dfs(i-1,j)+dfs(i,j+1)+dfs(i,j-1);