贪心算法.cpp

来自「这是一个贪心算法的c程序。贪心算法（也叫贪婪算法）不是某种特定的算法」· C++ 代码 · 共 108 行

#include "stdio.h"
class horse
{
public:
    horse(int,int);
    ~horse();
    void solve(int,int);
protected:
    void dfs(int,int,int);
    int **data;
    int *head;
    int width;
    int height;
    int size;
    int count;
};
struct hnode
{
    int x;
    int y;
    int weight;
};
horse::horse(int n,int m)
{
    width=n;
    height=m;
    size=n*m;
    head=new int[size];
    data=new int*[m];
    for(int i=0;i<m;++i)
    {
        data[i]=head+i*n;
        for(int j=0;j<n;++j)
            data[i][j]=0;
    }
}
horse::~horse()
{
    delete[] data;
    delete[] head;
}
void horse::solve(int x,int y)
{
    try
    {
        count=0;
        dfs(x,y,1);
        printf("无解!\n回溯%d次\n",count);
    }
    catch(int)
    {
        for(int i=0;i<height;++i)
        {
            printf("\n");
            for(int j=0;j<width;++j)
                printf(" %02d",data[i][j]);
        }
        printf("\n回溯%d次\n",count);
    }
}
void horse::dfs(int x,int y,int c)
{
    static int dx[8]={-1,-1,1,1,-2,-2,2,2};
    static int dy[8]={-2,2,-2,2,-1,1,-1,1};
    hnode hn[8];
    data[y][x]=c;
    if(c==size)throw(1);
    for(int i=0;i<8;++i)
    {
        int tx,ty;
        hn[i].x=tx=x+dx[i];
        hn[i].y=ty=y+dy[i];
        if(tx<0||tx>=width||ty<0||ty>=height||data[ty][tx]>0)
        {
            hn[i].weight=-1;continue;
        }
        hn[i].weight=0;
        for(int j=0;j<8;++j)
        {
            int mx,my;
            mx=tx+dx[j];
            my=ty+dy[j];
            if(mx>=0&&mx<width&&my>=0&&my<height&&data[my][mx]==0)
                hn[i].weight++;
        }
        if(hn[i].weight==0)
            hn[i].weight=9;
    }
    for(i=0;i<7;++i)
        for(int j=i+1;j<8;++j)
            if(hn[i].weight>hn[j].weight)
            {
                hnode temp=hn[i];
                hn[i]=hn[j];
                hn[j]=temp;
            }
    for(i=0;i<8;++i)
        if(hn[i].weight>0)
            dfs(hn[i].x,hn[i].y,c+1);
    data[y][x]=0;
    ++count;//回溯次数
}
void main()
{
    horse a(8,9);//width=8 * height=9的盘棋
    a.solve(0,0);//初始棋子位置
}