Опытный
Профиль
Группа: Участник
Сообщений: 379
Регистрация: 9.11.2005
Репутация: 26
Всего: 31
|
С примером... main.h: | Код |
//---------------------------------------------------------------------------
#ifndef mainH
#define mainH
//---------------------------------------------------------------------------
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
#include <ExtCtrls.hpp>
//---------------------------------------------------------------------------
class TfrmMain : public TForm
{
__published: // IDE-managed Components
TGroupBox *gbxData;
TGroupBox *gbxStart;
TGroupBox *gbxFinish;
TComboBox *cbxStartX;
TComboBox *cbxStartY;
TComboBox *cbxFinishX;
TComboBox *cbxFinishY;
TButton *btnFind;
TGroupBox *gbxChessBoard;
TImage *imgChessBoard;
TGroupBox *gbxResult;
TListBox *lstResult;
void __fastcall FormPaint(TObject *Sender);
void __fastcall btnFindClick(TObject *Sender);
void __fastcall FormCreate(TObject *Sender);
private: // User declarations
public: // User declarations
__fastcall TfrmMain(TComponent* Owner);
void __fastcall InitChessBoard();
void __fastcall DrawChessBoard();
void __fastcall Wave(int x,int y,int cost);
int __fastcall GetCost(int x,int y);
bool __fastcall GetStep(int&x,int&y);
void __fastcall GetPath();
};
//---------------------------------------------------------------------------
extern PACKAGE TfrmMain *frmMain;
//---------------------------------------------------------------------------
#endif
|
main.cpp: | Код |
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "main.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TfrmMain *frmMain;
const int CHESS_BOARD_SIZE=8;//размерность доски
const int UNUSED_CELL=-1;//клетка не использована
int ChessBoard[CHESS_BOARD_SIZE][CHESS_BOARD_SIZE];//описание доски
void __fastcall TfrmMain::InitChessBoard()
//ф-ция инициализации доски
{
for(int i=0;i<CHESS_BOARD_SIZE;i++)
for(int j=0;j<CHESS_BOARD_SIZE;j++)
ChessBoard[i][j]=UNUSED_CELL;//отмечаем все ячейки, как не использованные
}
void __fastcall TfrmMain::DrawChessBoard()
//ф-ция прорисовки доски
{
RECT rect;
for(int i=0;i<CHESS_BOARD_SIZE;i++)
for(int j=0;j<CHESS_BOARD_SIZE;j++)
{
SetRect(&rect,i*21,j*21,(i+1)*21,(j+1)*21);//вычисляем положение ячейки
if((i+j)%2)//чередование цветов
{
imgChessBoard->Canvas->Brush->Color=RGB(255,255,255);//белый цвет кисти
}
else
{
imgChessBoard->Canvas->Brush->Color=RGB(0,0,0);//черный цвет кисти
}
imgChessBoard->Canvas->FillRect(rect);//заполняем прямоугольник
imgChessBoard->Canvas->Font->Size=12;//устанавливаем размер шрифта
if(ChessBoard[i][j]!=UNUSED_CELL)//если ячейка уже использовалась
{
imgChessBoard->Canvas->Font->Color=RGB(128,128,128);//устанавливаем цвет текста
imgChessBoard->Canvas->TextOutA(i*21,j*21,ChessBoard[i][j]);//выводим значение ячейки
}
}
if(cbxStartX->ItemIndex!=cbxFinishX->ItemIndex||cbxStartY->ItemIndex!=cbxFinishY->ItemIndex)
//если начальная и конечная позиция не совпадают
{
imgChessBoard->Canvas->Font->Color=RGB(255,0,0);//устанавливаем цвет текста
imgChessBoard->Canvas->TextOutA(cbxStartX->ItemIndex*21,cbxStartY->ItemIndex*21,"S");//S - start
imgChessBoard->Canvas->Font->Color=RGB(0,0,255);//устанавливаем цвет текста
imgChessBoard->Canvas->TextOutA(cbxFinishX->ItemIndex*21,cbxFinishY->ItemIndex*21,"F");//F - finish
}
}
void __fastcall TfrmMain::Wave(int x,int y,int cost)
//Ф-ция волны для ячейки
//Если положение (x,y) попадает на игровое поле, то
//если ячейка не использовалась или использовалась и её стоимость выше переданной(cost), то
//записываем в ячейку новое(меньшее значение) и проверяем всех соседей
{
if(x>=0&&x<CHESS_BOARD_SIZE&&y>=0&&y<CHESS_BOARD_SIZE)
{
if(ChessBoard[x][y]==UNUSED_CELL||(ChessBoard[x][y]!=UNUSED_CELL&&ChessBoard[x][y]>cost))
{
ChessBoard[x][y]=cost;
Wave(x-1,y-2,cost+1);
Wave(x+1,y-2,cost+1);
Wave(x+2,y-1,cost+1);
Wave(x+2,y+1,cost+1);
Wave(x+1,y+2,cost+1);
Wave(x-1,y+2,cost+1);
Wave(x-2,y+1,cost+1);
Wave(x-2,y-1,cost+1);
}
}
}
int __fastcall TfrmMain::GetCost(int x,int y)
//ф-ция возвращает значение ячейки, если (x,y) на поле или UNUSED_CELL иначе
{
if(x>=0&&x<CHESS_BOARD_SIZE&&y>=0&&y<CHESS_BOARD_SIZE)
{
return ChessBoard[x][y];
}
else
{
return UNUSED_CELL;
}
}
bool __fastcall TfrmMain::GetStep(int&x,int&y)
//ф-ция возвращает true, если в окрестности (x,y) найдена точка с меньшей стоимостью
//и если это не конечная точка, а также координаты ячейки с наименьшей стоимостью
{
int tempCost,tempx,tempy,newx,newy;
int cost=ChessBoard[x][y];//инициализация стоимости
bool bHaveResult=false;//инициализация переменной, отвечающей за нахождение след. ячейки
//далее проверяем всевозможные варианты хода коня
tempx=x-1;
tempy=y-2;
tempCost=GetCost(tempx,tempy);//вычисляем значение ячейки
if(tempCost!=UNUSED_CELL&&tempCost<cost)
//если ячейка использовалась и вычисленная стоимость ниже
{
cost=tempCost;//запоминаем новую мин. стоимость
newx=tempx;//запоминаем
newy=tempy;//координаты
bHaveResult=true;//ячейка успешно найдена
}
tempx=x+1;
tempy=y-2;
tempCost=GetCost(tempx,tempy);
if(tempCost!=UNUSED_CELL&&tempCost<cost)
{
cost=tempCost;
newx=tempx;
newy=tempy;
bHaveResult=true;
}
tempx=x+2;
tempy=y-1;
tempCost=GetCost(tempx,tempy);
if(tempCost!=UNUSED_CELL&&tempCost<cost)
{
cost=tempCost;
newx=tempx;
newy=tempy;
bHaveResult=true;
}
tempx=x+2;
tempy=y+1;
tempCost=GetCost(tempx,tempy);
if(tempCost!=UNUSED_CELL&&tempCost<cost)
{
cost=tempCost;
newx=tempx;
newy=tempy;
bHaveResult=true;
}
tempx=x+1;
tempy=y+2;
tempCost=GetCost(tempx,tempy);
if(tempCost!=UNUSED_CELL&&tempCost<cost)
{
cost=tempCost;
newx=tempx;
newy=tempy;
bHaveResult=true;
}
tempx=x-1;
tempy=y+2;
tempCost=GetCost(tempx,tempy);
if(tempCost!=UNUSED_CELL&&tempCost<cost)
{
cost=tempCost;
newx=tempx;
newy=tempy;
bHaveResult=true;
}
tempx=x-2;
tempy=y+1;
tempCost=GetCost(tempx,tempy);
if(tempCost!=UNUSED_CELL&&tempCost<cost)
{
cost=tempCost;
newx=tempx;
newy=tempy;
bHaveResult=true;
}
tempx=x-2;
tempy=y-1;
tempCost=GetCost(tempx,tempy);
if(tempCost!=UNUSED_CELL&&tempCost<cost)
{
cost=tempCost;
newx=tempx;
newy=tempy;
bHaveResult=true;
}
if(bHaveResult)//если есть хотя бы одна удовл. усл. ячейка
{
x=newx;//возвращаем x
y=newy;//возвращаем y
return !(x==cbxFinishX->ItemIndex&&y==cbxFinishY->ItemIndex);
//конечная ли позиция
}
else//нет ни одной ячейки
{
return false;
}
}
void __fastcall TfrmMain::GetPath()
//ф-ция строит путь по волне
{
int x,y,count;//x,y - координаты, count - кол-во шагов
AnsiString str;//вспомогательная переменная
x=cbxStartX->ItemIndex;//инициализируем
y=cbxStartY->ItemIndex;//переменные координатами начальной ячейки
count=0;//не было ни одного шага
lstResult->Clear();//очищаем листбокс
lstResult->AddItem("Path:",NULL);//Путь:
if(GetStep(x,y))//если в окрестности существует хотя бы одна ячейка, то путь существует
{
do
{
count++;//есть очередной шаг
str.sprintf("%i:%c%i",count,'a'+x,y+1);//записываем в строку
lstResult->AddItem(str,NULL);//добавляем строку в листбокс
}
while(GetStep(x,y));//пока есть след. шаг
count++;//последний шаг
str.sprintf("%i:%c%i",count,'a'+x,y+1);
lstResult->AddItem(str,NULL);
}
else
{
lstResult->AddItem("Path not found",NULL);//Пути нет
}
}
//---------------------------------------------------------------------------
__fastcall TfrmMain::TfrmMain(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TfrmMain::FormPaint(TObject *Sender)
{
DrawChessBoard();//перерисовываем доску
}
//---------------------------------------------------------------------------
void __fastcall TfrmMain::btnFindClick(TObject *Sender)
{
InitChessBoard();//инициализируем доску
DrawChessBoard();//рисуем доску
if(cbxStartX->ItemIndex!=cbxFinishX->ItemIndex||cbxStartY->ItemIndex!=cbxFinishY->ItemIndex)
//если нач. и конечн. позиция не совпадают
{
Wave(cbxFinishX->ItemIndex,cbxFinishY->ItemIndex,0);//Запускаем волну
DrawChessBoard();//рисуем доску
GetPath();//получаем путь
}
else
{
lstResult->Clear();//очищаем листбокс
lstResult->AddItem("Начальная и конечная точки совпадают",NULL);
}
}
//---------------------------------------------------------------------------
void __fastcall TfrmMain::FormCreate(TObject *Sender)
{
InitChessBoard();//инициализация доски
}
//---------------------------------------------------------------------------
|
ChessWave.rar 33,27 Kb |
[BCB] Найти наименьшее число ходов шахматным конём 
Загрузка ...
