Skip to content

Instantly share code, notes, and snippets.

@lin-ion

lin-ion/backtracking_matrix_path.cpp

Last active November 29, 2023 12:55
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save lin-ion/ec4627e41dee146062828f691a8158d1 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save lin-ion/ec4627e41dee146062828f691a8158d1 to your computer and use it in GitHub Desktop.
Download ZIP
dynprog
Raw
backtracking_matrix_path.cpp
#include <iostream>
#include <array>
#include <algorithm>
using std::array, std::max, std::cout, std::endl;
template<class T, size_t Col, size_t Row>
void optimization(array<array<T, Col>, Row> m)
{
array<array<T, Col>, Row> c{};
c[0][0] = m[0][0];
for (size_t i = 1; i < Row; ++i)
{
c[i][0] = m[i][0] + c[i - 1][0];
}
for (size_t j = 1; j < Col; ++j)
{
c[0][j] = m[0][j] + c[0][j - 1];
}
for (size_t i = 1; i < Row; ++i)
{
for (size_t j = 1; j < Col; ++j)
{
c[i][j] = m[i][j] + max(c[i - 1][j], c[i][j - 1]); // 같은 값에선 상/하로 이동
}
}
cout << "Max = " << c[Row - 1][Col - 1] << endl;
{
size_t i = Row-1;
size_t j = Col-1;
array<array<size_t, 2>, Row + Col - 1> path{};
int p = path.size()-1;
path[p] = { i,j };
while (i > 0 && j > 0)
{
if (c[i - 1][j] >= c[i][j - 1])
{
path[--p] = { --i,j };
}
else
{
path[--p] = { i,--j };
}
}
while (i > 0)
{
path[--p] = { --i,j };
}
while (j > 0)
{
path[--p] = { i,--j };
}
for (auto p : path)
{
cout << "(" << p[1]+1 << "," << p[0]+1 << ") ";
}
cout << endl;
}
}
int main()
{
constexpr array<array<int, 4>, 4> m{ {
{6,7,12,5,},
{5,3,11,18,},
{7,17,3,3,},
{8,10,14,9,},
} };
optimization(m);
}
Raw
backtracking_pebble.cpp
#include <iostream>
#include <array>
#include <algorithm>
using std::array, std::max, std::cout, std::endl;
template<class T, size_t Col, size_t Row>
void optimization(array<array<T, Col>, Row> m)
{
array<array<T, 4>, Col> c{ {
{m[0][0], },
{m[1][0], },
{m[2][0], },
{m[0][0] + m[2][0], },
} };
for (size_t i = 1; i < Col;++i)
{
c[0][i] = m[0][i] + max({ c[1][i - 1], c[2][i - 1] });
c[1][i] = m[1][i] + max({ c[0][i - 1], c[2][i - 1], c[3][i - 1] });
c[2][i] = m[2][i] + max({ c[0][i - 1], c[1][i - 1] });
c[3][i] = m[0][i] + m[2][i] + max({ c[1][i - 1] });
};
T result = max({ c[0][Col - 1], c[1][Col - 1], c[2][Col - 1], c[3][Col - 1] });
cout << "Max = " << result << endl;
{
array<size_t, Col> path{};
for (size_t p = 0; p < 4; ++p)
{
if (result == c[p][Col - 1])
{
path[Col - 1] = p;
break;
}
}
for (size_t i = Col - 1; i >= 1; --i)
{
size_t pattern = path[i];
if (pattern == 3)
{
path[i - 1] = 1;
continue;
}
T diff = c[pattern][i] - m[pattern][i];
if (pattern == 0)
{
if (diff == c[1][i - 1]) { path[i - 1] = 1; }
else { path[i - 1] = 2; }
}
else if (pattern == 1)
{
if (diff == c[0][i - 1]) { path[i - 1] = 0; }
else if (diff == c[2][i - 1]) { path[i - 1] = 2; }
else { path[i - 1] = 3; }
}
else
{
if (diff == c[0][i - 1]) { path[i - 1] = 0; }
else { path[i - 1] = 2; }
}
}
cout << "Path = ";
for (auto p : path)
{
cout << "(" << int(p + 1) << ") ";
}
cout << endl;
}
}
int main()
{
constexpr array<array<int, 8>, 3> m{ {
{6,7,12,-5,5,3,11,3},
{-8,10,14,9,7,13,8,5},
{11,12,7,4,8,-2,9,4}
} };
optimization(m);
}
Raw
matrix_path.cpp
#include <iostream>
#include <array>
#include <algorithm>
using std::array, std::max, std::cout, std::endl;
template<class T, size_t Col, size_t Row>
T optimization(array<array<T, Col>, Row> m)
{
array<array<T, Col>, Row> c{};
c[0][0] = m[0][0];
for (size_t i = 1; i < Row; ++i)
{
c[i][0] = m[i][0] + c[i - 1][0];
}
for (size_t j = 1; j < Col; ++j)
{
c[0][j] = m[0][j] + c[0][j - 1];
}
for (size_t i = 1; i < Row; ++i)
{
for (size_t j = 1; j < Col; ++j)
{
c[i][j] = m[i][j] + max(c[i - 1][j], c[i][j - 1]);
}
}
return c[Row - 1][Col - 1];
}
int main()
{
constexpr array<array<int, 4>, 4> m{ {
{6,7,12,5,},
{5,3,11,18,},
{7,17,3,3,},
{8,10,14,9,},
} };
cout << "Max = " << optimization(m) << endl;
}
Raw
pebble.cpp
#include <iostream>
#include <array>
#include <algorithm>
using std::array, std::max, std::cout, std::endl;
template<class T, size_t Col, size_t Row>
T optimization(array<array<T, Col>, Row> m)
{
array<array<T, 4>, Col> c{ {
{m[0][0], },
{m[1][0], },
{m[2][0], },
{m[0][0] + m[2][0], },
} };
for (size_t i = 1; i < Col;++i)
{
c[0][i] = m[0][i] + max({ c[1][i - 1], c[2][i - 1] });
c[1][i] = m[1][i] + max({ c[0][i - 1], c[2][i - 1], c[3][i - 1] });
c[2][i] = m[2][i] + max({ c[0][i - 1], c[1][i - 1] });
c[3][i] = m[0][i] + m[2][i] + c[1][i - 1];
};
return max({ c[0][Col - 1], c[1][Col - 1], c[2][Col - 1], c[3][Col - 1] });
}
int main()
{
constexpr array<array<int, 8>, 3> m{ {
{6,7,12,-5,5,3,11,3},
{-8,10,14,9,7,13,8,5},
{11,12,7,4,8,-2,9,4},
} };
cout << "Max = " << optimization(m) << endl;
}
@lin-ion
Copy link
Author

lin-ion commented Nov 23, 2023 •
edited
Loading 

line@LINE:~$ ./matrix_path 
Max = 68
line@LINE:~$ ./pebble
Max = 106

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment