leetcode52.N皇后 II

矫情吗；* 2022-09-08 11:31 169阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_11_color_FFFFFF_t_70_g_se_x_16]  
思路

1.  经典回溯和526以及其他全排列一致
2.  （符合条件的）可放可不放问题
3.  使用`a[hang] = lie`进行标记，`a[hang]`可以放置列号`1-n`中的任意一个，但是前提是符合不在一行（这个已经利用数组搞定了），不在一列，而且也不在同一斜线

void backtrack(路径,选择列表)
    { 
    	if(满足条件){ 
    		result.add(路径)||result++;
    		return;
    	}
    	for(选择in选择列表){ 
    	//if(满足放置条件)
    		做选择;
    		backtrack(路径,选择列表);
    		撤销选择;
    	}
    }

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    int canput(int *a,int hang,int lie){ 
        int i;
        for(i=1;i<hang;i++){ //，在已经放过的行号每个进行比较，列不一样，而且不在一斜线
            if(a[i]==lie||abs(hang-i)==abs(lie-a[i])){ 
                return 0;
            }
        }
        return 1;
    }
    
    void put(int *a,int hang,int end,int *count){ 
        int i;
        if(hang>end){ 
            (*count)++;
            return;
        }
        for(i=1;i<=end;i++){ 
            if(canput(a,hang,i)){ 
                a[hang] = i;
                put(a,hang+1,end,count);
                a[hang] = -1;
            }
        }
    }
    int totalNQueens(int n){ 
        int a[n+1];
        memset(a,-1,sizeof(a));
        int count=0;
        put(a,1,n,&count);
        return count;
    }
    
    int main(){ 
        int res = totalNQueens(4);
        printf("re = %d\n",res);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/c43f82d4ae6540e2a63c384f5d7537a6.png