-
N皇后問題
定義： n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上蛀柴，并且使皇后彼此之間不能相互攻擊。
1.八皇后問題：
細(xì)節(jié)：
- 皇后和象棋中的<王>或者<士>類似嘀倒，可以走直線或者對角屈留。不同之處在于，<王>每步只能走一個單位测蘑，而皇后可以走任意長度灌危。
代碼：
DFS：
- 根據(jù)上一點，可知碳胳，在放好k行皇后乍狐，準(zhǔn)備放入k+1個皇后時，要與前k個分別檢測是否沖突固逗。
- 回溯：沖突檢測為false時浅蚪，DFS函數(shù)回立即返回，這可以看作是一種剪枝優(yōu)化烫罩。
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. 美團(tuán)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;
}
}
};
優(yōu)化：邊緣處理：
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);
