好几天没刷题, 罪过= =看推理动漫, 玩编程游戏去了= =

又是简单回溯, 注意和8皇后的区别.

1 #include 
     
       2 #include 
      
        3  4 using namespace std; 5  6 #define MAX_SIZE 10 7 int gn = 0; 8 char gmap[MAX_SIZE][MAX_SIZE] = {
   0}; 9 int gmax = 0;10 11 void dfs(int cur, int num) {12     if (cur == gn * gn) {13         if (num > gmax) {14             gmax = num;15         }16         return;17     }18     int x = cur / gn;19     int y = cur % gn;20     int flagx = 0;21     for (int i = x - 1; i >= 0; --i) if (gmap[i][y] != 'X') {22         if (gmap[i][y] == 'O') {23             flagx = 1;24             break;25         }26     } else {27         break;28     }29     int flagy = 0;30     for (int i = y - 1; i >= 0; --i) if (gmap[x][i] != 'X') {31         if (gmap[x][i] == 'O') {32             flagy = 1;33             break;34         }35     } else {36         break;37     }38     if (!flagx && !flagy && gmap[x][y] != 'X') {39         gmap[x][y] = 'O';40         dfs(cur + 1, num + 1);41         gmap[x][y] = '.';42         dfs(cur + 1, num);43     } else {44         dfs(cur + 1, num);45     }46 }47 48 int main(int argc, const char * argv[])49 {50     while (scanf("%d\n", &gn)) {51         if (gn == 0) {52             break;53         }54         gmax = 0;55         for (int i = 0; i < gn; ++i) {56             for (int j = 0; j < gn; ++j) {57                 scanf("%c", &gmap[i][j]);58             }59             getchar();60         }61         dfs(0, 0);62         printf("%d\n", gmax);63     }64     return 0;65 }