Не волновой, тупой перебор, да я его еще и не тестил:
| Код |
#include<iostream>
#include<conio.h>
using namespace std;
void InputMatrix(int** Matrix,int dim)
//ввод квадратной матрицы размерности dim x dim
{
for(int i=0;i<dim;i++)
for(int j=0;j<dim;j++)
cin>>Matrix[i][j];
}
void PrintMatrix(int** Matrix,int dim)
//печать квадратной матрицы размерности dim x dim
{
for(int i=0;i<dim;i++)
{
for(int j=0;j<dim-1;j++)
cout<<Matrix[i][j]<<" ";
cout<<Matrix[i][dim-1]<<"\n";
}
}
void FindMinPath(int** Matrix,int dim,int i,int j,int step,int sum,int& bestsum)
{
sum+=Matrix[i][j];//добавляем значение ячейки
if(step<dim*dim&&(sum<bestsum||!bestsum))//ходов не может быть больше, чем размерность в квадрате
{
if(i==dim-1&&j==dim-1)//если правый нижний угол
{
bestsum=sum;//запоминаем лучшее значение
}
else
{
step++;//увеличение шага
if(i)FindMinPath(Matrix,dim,i-1,j,step,sum,bestsum);//для левой ячейки
if(j)FindMinPath(Matrix,dim,i,j-1,step,sum,bestsum);//для нижней ячейки
if(i<dim-1)FindMinPath(Matrix,dim,i+1,j,step,sum,bestsum);//для правой ячейки
if(j<dim-1)FindMinPath(Matrix,dim,i,j+1,step,sum,bestsum);//для верхней ячейки
}
}
}
int main()
{
int dim,bestsum=0;//dim -размерность, bestsum - лучший результат
cout<<"Please enter a dimensionality:\n";
cin>>dim;//ввод размерности
int** Matrix;//указатель на матрицу
Matrix=new int*[dim];
for(int i=0;i<dim;i++)
Matrix[i]=new int[dim];
cout<<"Please enter a matrix("<<dim<<"x"<<dim<<"):\n";
InputMatrix(Matrix,dim);
cout<<"Source matrix:\n";
PrintMatrix(Matrix,dim);
FindMinPath(Matrix,dim,0,0,0,0,bestsum);//рекурсивный поиск
for(int i=0;i<dim;i++)
delete[] Matrix[i];
delete[] Matrix;
cout<<"Min path="<<bestsum<<"\n";//вывод результата
getch();
return 0;
}
|
P.S. надеюсь работает |
