alver,
ты первый раз С/С++ видишь?
| Код |
#include <vector>
#include <map>
typedef std :: vector<std :: vector<bool>> matrix_t;
typedef std :: pair<int, int> coord_t;
typedef std :: vector<coord_t> stack_t;
bool operator==(const coord_t& a, const coord_t& b)
{
return a.first == b.first && a.second == b.second;
}
bool bad_range(coord_t& coord, matrix_t& matrix) {
return coord.first < 0 || coord.first >= matrix.size() ||
coord.second < 0 || coord.second >= matrix[0].size();
}
int runs[4][2] = {{0, 1},{1, 0},{0, -1},{-1, 0}};
void find(matrix_t& matrix, coord_t current, coord_t& end, bool& flags, stack_t& stack)
{
if (current == end)
{
stack.push_back(current);
flags = true;
return;
}
if (bad_range(current, matrix) || !matrix[current.first][current.second])
return;
for (int i = 0; i < 4; ++i)
{
coord_t tmp = current;
tmp.first+= runs[i][0];
tmp.second+= runs[i][1];
if (!bad_range(tmp, matrix))
{
matrix[current.first][current.second] = false;
stack.push_back(current);
find(matrix, tmp, end, flags, stack);
if (flags) break;
stack.pop_back();
matrix[current.first][current.second] = true;
}
}
}
int main() {
// тут вводишь свою матрицу и вызываешь find()
return 0;
}
|
если не получится позже напишу, сейчас времени нет |