guohe.cpp

关于数据结构的各章节的c原代码实现

// guohe.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream.h>
#include <stdlib.h>
bool matrix[5][5],turn;
int record[128][2],pos=1;
bool check[128];
/*判断这一状态是否在前面已经出现过*/
bool isRepeat(int x,int y,bool turn)
{
    for(int i=0;i<pos;i++)
        if(x==record[i][0]&&y==record[i][1]&&turn==check[i])
            return true;
		return false;
}
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++)
        {
 cout<<"("<<record[i][0]<<","<<record[i][1]<<")<==>("<<4-record[i][0]<<","<<4-record[i][1]<<")"<<endl;
        }
        //system("pause");
		exit(1);
    }
    else if(turn==false)
    {
        for(i=0;i<5;i++)
        {
            px-=goStep[i][0];
            py-=goStep[i][1];
            if(px<0||px>4||py<0||py>4||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==true?false:true);
            search(px,py);
            pos--;
            turn=(turn==true?false:true);
            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>4||py<0||py>4||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==true?false:true);
            search(px,py);
            pos--;
            turn=(turn==true?false:true);
            px-=goStep[i][0];
            py-=goStep[i][1];
        }
    }
}
int main(int argc, char* argv[])
{
    int px=4,py=4;
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
        {
            if(i==j||i==0||i==4);
            else matrix[i][j]=true;
        }
		record[0][0]=record[0][1]=4;
		check[0]=true;
		search(px,py);
		if (px!=0||py!=0)
		{
			cout<<"无解!"<<endl;
		}
		return 0;
}