| Код |
struct coords
{
int x,y;
coords(int p_x=0, int p_y=0): x(p_x), y(p_y) {}
};
class Stack
{
private:
coords array[1024]; // Чтоб не мучаться с дин. массивом
int index;
public:
Stack(): index(0) {}
void push(const coords& obj)
{
if (index<=1024) array[index++]=obj;
}
coords pop() {if (index-1>=0) --index;}
Stack& operator=(const Stack& obj)
{
index=obj.index;
for (int i=0; i<index; ++i) array[i]=obj.array[i];
}
void Print()
{
for (int i=0; i<index; ++i) std::cout<<"x="<<array[i].x<<", y="<<array[i].y<<std::endl;
}
};
...
void find(bool **field, int& sum, int i, int j, int s, Stack& primary, Stack& current)
{
if (i<0 || i>=n || j<0 || j>=m)
return;
if (i==n-1)
{
if (s+matrix[i][j]>sum)
{
sum=s+matrix[i][j];
primary=current;
}
return;
}
if (!field[i][j])
{
field[i][j]=true;
current.push(coords(i,j));
int temp=s+matrix[i][j];
find(field,sum,i+1,j,temp,primary,current);
find(field,sum,i+1,j-1,temp,primary,current);
find(field,sum,i+1,j+1,temp,primary,current);
current.pop();
field[i][j]=false;
}
}
|
Добавлено @ 09:46
вся прога
| Код |
#include <iostream>
#include <math.h>
using std::cout;
using std::cin;
using std::endl;
struct coords
{
int x,y;
coords(int p_x=0, int p_y=0): x(p_x), y(p_y) {}
};
class Stack
{
private:
coords array[1024]; // Чтоб не мучаться с дин. массивом
int index;
public:
Stack(): index(0) {}
void push(const coords& obj)
{
if (index<=1024) array[index++]=obj;
}
coords pop() {if (index-1>=0) --index;}
Stack& operator=(const Stack& obj)
{
index=obj.index;
for (int i=0; i<index; ++i) array[i]=obj.array[i];
}
void Print()
{
for (int i=0; i<index; ++i) std::cout<<"x="<<array[i].x<<", y="<<array[i].y<<std::endl;
}
};
const int n=4;
const int m=5;
int matrix[n][m];
void Getmatr (int, int); //матрица из случайных чисел
void Myprint (int, int); //выводит матрицу
void find(bool**, int&, int, int, int, Stack&, Stack&);
int main()
{
int sum=0;
bool **field; //двумерное "поле"
field =new bool*[n];
for (int i=0; i<n; i++)
{
field[i]=new bool[m];
for (int j=0; j<n; j++) field[i][j]=false; // Первоначально никакую клетку не посетили
}
Getmatr(n,m);
Stack c;
for (int i=0; i<m; i++) // Проходим по элементам первой строки
{
int temp_sum=0;
Stack a,b;
find(field,temp_sum,0,i,0,a,b);
if (temp_sum>sum)
{
sum=temp_sum;
c=a;
}
}
Myprint(n,m);
cout<<"Max: "<<sum<<endl;
c.Print();
int a;
cin>>a;
for (int i=0; i<n; i++)
delete []field[i];
delete []field;
return 0;
}
void Getmatr (int n, int m)
{
int RANGE_MIN=0;
int RANGE_MAX=10;
srand((unsigned)time(NULL));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
matrix[i][j]=
static_cast<int>(((double)rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
}
}
void Myprint (int n, int m)
{
for(int i=0;i<n;i++)
{
cout<<endl;
for(int j=0;j<m;j++)
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
void find(bool **field, int& sum, int i, int j, int s, Stack& primary, Stack& current)
{
if (i<0 || i>=n || j<0 || j>=m)
return;
if (i==n-1)
{
if (s+matrix[i][j]>sum)
{
sum=s+matrix[i][j];
primary=current;
primary.push(coords(j,i));
}
return;
}
if (!field[i][j])
{
field[i][j]=true;
current.push(coords(j,i));
int temp=s+matrix[i][j];
find(field,sum,i+1,j,temp,primary,current);
find(field,sum,i+1,j-1,temp,primary,current);
find(field,sum,i+1,j+1,temp,primary,current);
current.pop();
field[i][j]=false;
}
}
|
|
Это круто!!! 