2011-08-16 21:21:19Morris
a160. 變態想要下棋!!!
a160. 柏森想要下棋!!!
/**********************************************************************************/
/* Problem: a160 "柏森想要下棋!!!" from 上課數學課的胡思亂想 */
/* Language: C */
/* Result: AC (14ms, 236KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-16 16:54:11 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int n, row[13] = {}, map[13][13] = {};
int s[13], time;
int check(int x, int y) {
int a;
for(a = 0; a < x; a++)
if(abs(x-a) == abs(y-s[a])) return 0;
return 1;
}
int Print() {
int a, b;
for(a = 0; a < n; a++, puts(""))
for(b = 0; b < n; b++)
printf("%c", map[a][b] ? 'Q': 'x');
puts("");
}
void DFS(int now) {
if(now == n) {
time++, Print();
return;
}
int a;
for(a = 0; a < n; a++)
if(row[a] == 0 && check(now, a) == 1) {
row[a] = 1, map[now][a] = 1, s[now] = a;
DFS(now+1);
row[a] = 0, map[now][a] = 0;
}
}
main() {
while(scanf("%d", &n) == 1 && n)
time = 0, DFS(0), printf("%d\n", time);
return 0;
}
內容 :
從前有一個很會數學又很會寫程式的小小九年級生。
他的名子叫邱柏森。
他很愛下西洋棋
有一天他在寫程式的時候剛好碰到了一種同樣有關西洋棋的題目。
就是傳說中初學者在學DFS的時候一定要學的東西。
就是"八皇后"。
他遇到了困難,寫不出來。
請各位好心人寫一個程式幫幫他。
:)
輸入說明
:
輸入一個整數N,(0<N<12)
當N=0時結束程式。
輸出說明
:
把所有可能的解法用棋盤的方式印出來。
用'x' 代表空格以及'Q'來代表皇后。
記的要在最後輸出總共有幾組解法。
(注意我的範例輸出,這一題在間隔上是嚴格比對)
用'x' 代表空格以及'Q'來代表皇后。
記的要在最後輸出總共有幾組解法。
(注意我的範例輸出,這一題在間隔上是嚴格比對)
範例輸入 :
1 2 3 4 0
範例輸出 :
Q 1 0 0 xQxx xxxQ Qxxx xxQx xxQx Qxxx xxxQ xQxx 2
提示
:
要有很大的異次元才會AC喔。
這是小的第二次出題。
有任何意見歡迎提供。
出處
:
/**********************************************************************************/
/* Problem: a160 "柏森想要下棋!!!" from 上課數學課的胡思亂想 */
/* Language: C */
/* Result: AC (14ms, 236KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-16 16:54:11 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int n, row[13] = {}, map[13][13] = {};
int s[13], time;
int check(int x, int y) {
int a;
for(a = 0; a < x; a++)
if(abs(x-a) == abs(y-s[a])) return 0;
return 1;
}
int Print() {
int a, b;
for(a = 0; a < n; a++, puts(""))
for(b = 0; b < n; b++)
printf("%c", map[a][b] ? 'Q': 'x');
puts("");
}
void DFS(int now) {
if(now == n) {
time++, Print();
return;
}
int a;
for(a = 0; a < n; a++)
if(row[a] == 0 && check(now, a) == 1) {
row[a] = 1, map[now][a] = 1, s[now] = a;
DFS(now+1);
row[a] = 0, map[now][a] = 0;
}
}
main() {
while(scanf("%d", &n) == 1 && n)
time = 0, DFS(0), printf("%d\n", time);
return 0;
}
上一篇:d522. 走棋盘
下一篇:a141. 變態想要學妹!!!