在一个n*n个方格组成的棋盘上的任一方格中放置一个皇后，该皇后可以控制所在的行、列以及对角线上的所有方格。 
对于给定的自然数n（1<=n<=100），在n*n个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格，且放置的皇后互不攻击？ 

输入一个正整数n（1<=n<=100）

第1行是最少皇后数 
第2行是皇后的最佳放置方案

样例输出说明： 
1 为最少只需要放置一个皇后 
0 2 0： 
第一行不放置皇后 
第二行放置于第二列 
第三行不放置皇后 

网络19级算法设计与分析期末考试