商人过河.c

最优化的一系列算法

#include <stdio.h>
#include <stdlib.h>
int matrix[4][4],turn;
int record[128][2],pos=1;
int check[128];
/*判断这一状态是否在前面已经出现过*/
int isRepeat(int x,int y,int turn)
{
    int i;
    for(i=0;i<pos;i++)
        if(x==record[i][0]&&y==record[i][1]&&turn==check[i])
            return 1;
    return 0;
}
void search(int px,int py)
{
    static int goStep[5][2]={{0,2},{1,1},{2,0},{0,1},{1,0}};
    int i;
    if(px==0&&py==0)
    {
        for(i=0;i<pos;i++)
        {
            printf("("(%d,%d)<==>("%d,%d",record[i][0],record[i][1],3-record[i][0],3-record[i][1]);
        }
        system("pause");
    }
    else if(turn==0)
    {
        for(i=0;i<5;i++)
        {
            px-=goStep[i][0];
            py-=goStep[i][1];
            if(px<0||px>3||py<0||py>3||matrix[px][py]||isRepeat(px,py,turn))
            {
                px+=goStep[i][0];
              py+=goStep[i][1];
                continue;
            }
            record[pos][0]=px,record[pos][1]=py;
            check[pos]=turn;
            pos++;
            turn=(turn==1?0:1);
            search(px,py);
            pos--;
            turn=(turn==1?0:1);
            px+=goStep[i][0];
            py+=goStep[i][1];
        }
    }
    else
    {
        for(i=0;i<5;i++)
        {
            px+=goStep[i][0];
            py+=goStep[i][1];
            if(px<0||px>3||py<0||py>3||matrix[px][py]||isRepeat(px,py,turn))
            {
                px-=goStep[i][0];
                py-=goStep[i][1];
                continue;
            }
            record[pos][0]=px,record[pos][1]=py;
            check[pos]=turn;
            pos++;
            turn=(turn==1?0:1);
            search(px,py);
            pos--;
            turn=(turn==1?0:1);
            px-=goStep[i][0];
            py-=goStep[i][1];
        }
    }
}
int main()
{
    int px=3,py=3,i;
    for(i=0;i<4;i++)
        for(int j=0;j<4;j++)
        {
            if(i==j||i==0||i==3);
            else matrix[i][j]=1;
        }
    record[0][0]=record[0][1]=3;
    check[0]=1;
    search(px,py);
    return 0;
}