• API
• FAQ
• Tools
• Archive
daily pastebin goal
26%
SHARE
TWEET

# MH

a guest Oct 7th, 2009 127 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2. ID: teh_min1
3. PROG: checker
4. LANG: C
5. Checker Challenge
6. Done by Teh Ming Han
7. */
8.
9. /*
10. Algorithm: Recursion
11.
12. Notes:
13. If n is even, we can compute half a board and then flip along the x axis to generate the other half of the board.
14. this means we only need to generate half the board if n is even.
15.
16. If n is odd, we compute half a board and then (half + 1 rows) of the board.
17. Then we sum then up to get the answer.
18.
19. */
20.
21. #include <stdio.h>
22. #include <string.h>
23.
24. //#include <iostream.h>
25.
26. int ans[3][14] = {0}, ans_c = 0;
27.
28. int board[14] = {0}, n, size;
29.
30. int recur(int r){
31.     if (r==size){ //jackpot
32.         if (ans_c<3) memcpy(ans[ans_c],board,sizeof(int)*size);
33.         ans_c++;
34.         return 0;
35.     }
36.
37.     int a;
38.     char cans[28] = {'#'};
39.
40.     for (a=1;a<r;a++){
41.         cans[board[a]] = '@';
42.         cans[board[a]-(r-a)] = '@';
43.         cans[board[a]+(r-a)] = '@';
44.     }
45.
46.     for (a=1;a<=n;a++) //start checking if position is suitable
47.         if (cans[a]!='@'){
48.             board[r] = a;
49.             recur(r+1);
50.         }
51.
52.     return 0;
53. }
54.
55. int main(){
56.
57.     int i,a;
58.
59.     FILE * in = fopen("checker.in","r");
60.     fscanf(in,"%d",&n);
61.     fclose(in);
62.
63.     size = n + 1;
64.
65.     int ans_temp,limit;
66.
67.     if (n==6) limit = n;
68.     else limit = (n+1)/2;
69.
70.     for (i=1;i<=limit;i++){
71.         ans_temp = ans_c;
72.
73.         board[1] = i;
74.         recur(2);
75.     }
76.
77.     if (n%2==0 && n>6) ans_c *= 2;
78.     else if (n%2==1 && n>6) ans_c = ans_c + ans_temp;
79.
80.     FILE *out = fopen ("checker.out", "w");
81.
82.     for (i=0;i<3;i++){
83.         for (a=1;a<n;a++)
84.             fprintf(out,"%d ",ans[i][a]);
85.         fprintf(out,"%d\n",ans[i][n]); //solve the spacing prob
86.     }
87.     fprintf(out,"%d\n",ans_c);
88.     printf("%d\n",ans_c);
89.     fclose(out);
90.
91.     return 0;
92. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top