商人渡河问题:C语言实现

问题描述:
M个商人和N个随从将要从A岸渡河到B岸,m>=n
由于渡船最多载客K个,K>=2,因此需要多次往返渡河。
每次渡河时穿上必须至少有一个人。
随从密谋当任何一岸有商人,且随从数量多于商人时,随从就杀人越货
请为商人制定安全的渡河方案

/*
*  CrossRiver.c
*  程序效果:
*  输入M,N,K,
*  若有渡河方案,则打印每步之后A岸的m,n值,并显示success (不保证是最佳方案)
*  若没有渡河方案,则打印每步尝试之后A岸的m,n值,并显示failed
*/

#include "stdio.h"

/* check函数返回的值,INVALID=人数为负数,DIE=随从杀人,OK=安全 */
#define OK      0
#define INVALID 1
#define DIE     2

/* in_stack 函数返回的值,REPEAT=已经出现过了这种状态,不用重复,否则递归陷入死循环,OK=未出现过这种状态 */
#define REPEAT  3

/* 是否成功渡河 */
#define SUCCESS 1
#define FAILED  0

int M,N,K,m,n;

int stack[0x10000][2];
int slen = 0;

int check(int m,int n){
    if(m<0||n<0||M<m||N<n){ return INVALID; } if(m>0&&n>m){
        return DIE;
    }else if(M>m&&(N-n)>(M-m)){
        return DIE;
    }
    return OK;
}

int instack_push(int m,int n){
    int i;
    for(i=0;i<slen;i++){ if(m==stack[i][0]&&n==stack[i][1]){ return REPEAT; } } stack[slen][0] = m; stack[slen][1] = n; slen++; return OK; } int back(); int go(){ int c_sum, c_m; for(c_sum=K;c_sum>0;c_sum--){
        for(c_m=0;c_m<=c_sum;c_m++){
            m -= c_m;
            n -= (c_sum-c_m);
            if(check(m,n)==OK){
                int slen_bak = slen;
                if(instack_push(m,n)==OK){
                    printf("go:   m=%d,n=%d\n",m,n);
                    if(m==0&&n==0){
                        return SUCCESS;
                    }else{
                        if(back()==SUCCESS) return SUCCESS;
                    }
                    slen = slen_bak;
                }
            }
            m += c_m;
            n += (c_sum-c_m);
        }
    }
    return FAILED;
}

int back(){
    int c_sum, c_m;
    for(c_sum=1;c_sum<=K;c_sum++){
        for(c_m=0;c_m<=c_sum;c_m++){
            m += c_m;
            n += (c_sum-c_m);
            if(check(m,n)==OK){
                printf("back: m=%d,n=%d\n",m,n);
                if(go()==SUCCESS) return SUCCESS;
            }
            m -= c_m;
            n -= (c_sum-c_m);
        }
    }
    return FAILED;
}

int cross(int M_in,int N_in,int K_in){
    M = M_in; N = N_in; K = K_in; m = M; n = N;
    stack[0][0] = m; stack[0][1] = n;
    slen = 1;
    return go();
}

int main(){
    int m,n,k;
    printf("m : ");
    scanf("%d",&m);
    printf("n : ");
    scanf("%d",&n);
    printf("k : ");
    scanf("%d",&k);
    while(getchar()!='\n');
    if(cross(m,n,k)==SUCCESS)
        printf("--------------success-------------\n");
    else
        printf("--------------failed -------------\n");
    getchar();
}