Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Минимальный путь передвижения коня


Автор: Nike3000 7.5.2009, 21:05
Здравствуйте!
Требуется решить данную задачу:
найти min путь передвижения коня по шахматной доске из 1 клетки во 2-ую

Не подскажите с чего начать реализацию??

Автор: maxdiver 7.5.2009, 22:29
Построить граф (вершины - клетки) и реализовать на нём обход в ширину.

Автор: Nike3000 8.5.2009, 13:04
Ну я знаю как это сделать руками..Нужно реализовать на компе...

Алгоритм такой:
 сначала строим вершиный графов (вершины-те клетки куда конь сможет сходить)
 после надо этот граф както вбить в матрицу, а потом уже там искать мин. путь от клетки1 до 2

Как вот вбить в матрицу граф?
клеток 8 на 8
формулы для хода у коня  такие:
upright(x+1,y-2)
upleft(x-1,y-2)
leftup(x-2,y-1)
leftdown(x-2,y+1)
rightup(x+2,y-1)
rightdown(x+2,y+1)
downleft(x-1,y+2)
downright(x+1,y+2)

Автор: aram90 16.5.2009, 08:32
В принципе, явно построить граф не обьязательно. Задачу можно решить и так - на матрице, оне все же будет задача на графах, но граф мы не построим явно. Я не понял что ты имеешь в виду: "вбить в матрицу граф". Вот код решения:
Код

#include <iostream>
#include <queue>
using namespace std;
int w[8][8];
bool visited[8][8]={0};
int parent_row[8][8];
int parent_col[8][8];
queue<int> q;
int drow[8]={+1,-1,-2,-2,+2,+2,-1,+1};
int dcol[8]={-2,-2,-1,+1,-1,+1,+2,+2};
void main()
{
    int row1,col1,row2,col2,row,col,next_row,next_col,k;
    cin>>row1>>col1>>row2>>col2;
    w[row1][col1]=0;
    visited[row1][col1]=true;
    q.push(row1);
    q.push(col1);
    while(!q.empty())
    {
        row=q.front(); q.pop();
        col=q.front(); q.pop();
        if(visited[row2][col2]) break;
        for(k=0;k<8;k++)
        {
            next_row=row+drow[k];
            next_col=col+dcol[k];
            if(next_row<0 || next_row>7 || next_col<0 || next_col>7 || visited[next_row][next_col]) continue;
            w[next_row][next_col]=w[row][col]+1;
            visited[next_row][next_col]=true;
            parent_row[next_row][next_col]=row;
            parent_col[next_row][next_col]=col;
            q.push(next_row);
            q.push(next_col);
        }
    }    
    cout<<w[row2][col2]<<endl;
    row=row2; col=col2;
    for(;;)
    {
        cout<<row<<' '<<col<<endl;
        if(row==row1 && col==col1) break;
        next_row=parent_row[row][col];
        next_col=parent_col[row][col];
        row=next_row;
        col=next_col;
    }
}

Это простой поиск в ширину (BFS) в графе, то есть на доске, который использует очередь.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)