Declare Function sprintf CDECL Lib"msvcrt"(buffer As *Byte, ...) As Long
Const M = 3 /* 宣教師の数 */ Const C = 3 /* 人食い人の数 */ Const B = 2 /* ボートの定員 */
Dim np As Long, solution As Long Dim mb[ELM((B+1)*(B+2)/2)] As Byte, cb[ELM((B+1)*(B+2)/2)] As Byte Dim mh[ELM(2*(M+1)*(C+1))] As Byte, ch[ELM(2*(M+1)*(C+1))] As Byte, flag[M,C] As Byte
Dim sss[999] As Byte solution = solution + 1 Print "解"; solution i=0 While i <= n sprintf(sss, Ex"%4d %-*.*s %-*.*s / %-*.*s %-*.*s\n", _ i, M, mh[i], mmm, C, ch[i], ccc, _ M, M - mh[i], mmm, C, C - ch[i], ccc) i=i+1 Print MakeStr(sss) Wend End Sub
Dim static_i As Long Sub try() /* 再帰的に試す */
static_i = 0 Dim j As Long, m As Long, c As Long static_i = static_i + 1 j = 1 While j < np If (static_i And 1) Then /* 奇数回目は向こうに行く */ m = mh[static_i - 1] - mb[j]: c = ch[static_i - 1] - cb[j] Else /* 偶数回目はこちらに来る */ m = mh[static_i - 1] + mb[j]: c = ch[static_i - 1] + cb[j] End If if (m < 0 Or c < 0 Or m > M Or c > C Or (flag[m,c] And (1 << (static_i And 1)))) Then *CONT mh[static_i] = m: ch[static_i] = c If (m = 0 And c = 0) Then found(static_i) Else flag[m,c] = flag[m,c] Or (1 << (static_i And 1)): try() flag[m,c] = flag[m,c] Xor (1 << (static_i And 1)) End If *CONT j = j + 1 Wend static_i = static_i - 1 End Sub
Dim m As Long, c As Long np = 0 m = 0 While m <= B c = 0 While c <= B - m If (m = 0 Or m >= c) Then mb[np] = m: cb[np] = c: np++ End If c=c+1 Wend m=m+1 Wend
m=0 While m <= M c=0 While c <= C If ((m > 0 And m < c) Or (m < M And M - m < C - c)) Then flag[m,c] = flag[m,c] Or (1 Or 2) End If c=c+1 Wend m=m+1 Wend mh[0] = M: ch[0] = C: flag[M,C] = flag[M,C] Or 1 solution = 0: try() If (solution = 0) Then Print "解はありません."