/***********************************************************
cannibals.c -- 宣教師と人食い人
***********************************************************/
#N88BASIC
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 mmm[10] As *Byte, ccc[10] As *Byte
lstrcpy(mmm, "MMMMMMMMMM")
lstrcpy(ccc, "CCCCCCCCCC")
Sub found(n As Long) /* 解の表示 */
Dim i As Long
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 "解はありません."
