求一源程序

mawav

问题描述
在给定大小的方格状棋盘上, 将棋子”马”放在指定的起始位置 , 棋子”马” 的走子的规则为必须在棋盘上走”日”字; 从棋子”马”的起始位置开始, 搜索出一条可行的路径, 使得棋子”马”能走遍棋盘上的所有落子点, 而且每个落子点只能走一次;

例如: 棋盘大小为5*5 , 棋子马放的起始落子点为 ( 3 , 3 ) ; 算法需要搜索一条从位置( 3 , 3 ) 开始的一条包括从( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 3 ) … ( 5 , 1 ) , ( 5 , 2 ) , ( 5 , 3 ) , ( 5 , 4 ) , ( 5 , 5 ) 总共25个可以落子的全部位置



不是我不想写，实在是不会，N多WARINGS 和ERRORS

郁闷  





帮帮忙哦

kernelxu

用回溯算法或贪心算法
看精华贴
http://bbs.chinaunix.net/forum/viewtopic.php?t=437639

有源代码。

mawav

先谢啦，

aero

唉，以前写的好好的。就防着这个时候可以马上贴上来。硬盘一灾，全丢了，人算比如天算啊。

zerozero_nine

// 丢了还可以再写, 5*5 太少了, 大一点才走得畅快.
// Dev-C
// console.cpp
// zerozero_nine@hotmail.com

#include <windows.h>;
using namespace std;

POINT screensize;
void clrscr()
{
        COORD coordScreen = { 0, 0 };
        DWORD cCharsWritten;
        CONSOLE_SCREEN_BUFFER_INFO csbi;
        DWORD dwConSize;
        HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
  
        GetConsoleScreenBufferInfo(hConsole, &csbi);
        dwConSize = csbi.dwSize.X * csbi.dwSize.Y;
        screensize.x = csbi.dwSize.X;
        screensize.y = csbi.dwSize.Y;
        FillConsoleOutputCharacter(hConsole, TEXT(' '), dwConSize, coordScreen, &cCharsWritten);
        GetConsoleScreenBufferInfo(hConsole, &csbi);
        FillConsoleOutputAttribute(hConsole, csbi.wAttributes, dwConSize, coordScreen, &cCharsWritten);
        SetConsoleCursorPosition(hConsole, coordScreen);
}

void gotoxy(int x, int y)
{
        COORD point;
        if((x < 0 || x >; screensize.x) || (y < 0 || y >; screensize.y))
                return;
        point.X = x; point.Y = y;
        SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), point);
}

// Knight.cpp
#include <iostream>;
#include <functional>;
#include <vector>;
#include <queue>;
#include <time.h>;
#include <conio.h>;
#include "console.h"
using namespace std;

#define MAX_COL 20
#define MAX_ROW 20
#define COL_OFFSET (80-MAX_COL*4)/2
#define ROW_OFFSET (24-MAX_COL)/2
#define BACK_TRACK 0
#define RUN_COMPLETE 1
#define USER_BREAK 2
#define ESC 0x1B

#define INTPAIR pair<int, int>;

class Smaller {
public:
        bool operator()(const INTPAIR & x, const INTPAIR &y) {
                double xf,xs, yf, ys;
                xf=x.first-(MAX_COL-1)/2.0;
                xs=x.second-(MAX_ROW-1)/2.0;
                yf=y.first-(MAX_COL-1)/2.0;
                ys=y.second-(MAX_ROW-1)/2.0;
                return xf*xf+xs*xs<yf*yf+ys*ys;
        }
};

typedef priority_queue<INTPAIR, vector<INTPAIR>;, Smaller>; INTPAIRPQ;

int chess_board[MAX_COL][MAX_ROW];
int directions[][2]={{-1,-2},{-2,-1},{-1,2},{-2,1},{1,-2},{2,-1},{1,2},{2,1}};

bool valid_position(INTPAIR p)
{
        if (p.first<0||p.first>;=MAX_COL||p.second<0||p.second>;=MAX_ROW) return false;
        return (chess_board[p.first][p.second]==0);
}

int add_knight(int col, int row, int kno)
{
INTPAIR pos;
INTPAIRPQ steps;
int rc;
        chess_board[col][row]=kno;
        gotoxy(col*4+COL_OFFSET, row+ROW_OFFSET);
        printf(" %03d",kno);
        if (kno==MAX_COL*MAX_ROW) return RUN_COMPLETE;
        if ((kbhit() && getch()==ESC)) return USER_BREAK;
        for (int i=0;i<8;i++) {
                pos=make_pair(col+directions[0],row+directions[1]);
                if (valid_position(pos)) steps.push(pos);
        }
        while (steps.size()>;0) {
                pos=steps.top();
                steps.pop();
                if (rc=add_knight(pos.first, pos.second,kno+1)) return rc;
        }
        chess_board[col][row]=0;
        gotoxy(col*4+COL_OFFSET, row+ROW_OFFSET);
        printf("    ";
        return BACK_TRACK;
}

int main()
{
        clrscr();
        fill_n((int *)chess_board,MAX_COL*MAX_ROW,(int)0);
        srand(time(0));
        int rc=add_knight(rand()%MAX_COL,rand()%MAX_ROW,1);
        if (rc==RUN_COMPLETE) getch();
    return EXIT_SUCCESS;
}