На якій мові має бути реалізована програма? С або С++? Немає в завданні.
Де буде початок, координата [0,0]? Немає в завданні.
В завданні розмір лабіринту 6х6, а файл 8х8
У якому вигляді буде зберігатись лабіринт? Є в завданні.
Відкриваємо Visual Studio.
Створюємо новий консольний проект, маємо...
#include <iostream>
int main()
{
std::cout << "Hello World!\n";
}
Далі розбиваємо задачу на меньші задачі:
Прочитати дані з текстового файлу.
Створити лабіринт.
Отримати координати від користувача.
Перевірити правильність вводу.
Знайти вихід з лабіринту.
Оголошуємо необхідні функці:
#include <iostream>
//прочитати дані про лабіринт з текстового файлу
template <typename table>
bool ReadMaze(const std::string& fullPath, table& maze);
//отримати координати від користувача
template <typename table>
bool GetXY(unsigned int& x, unsigned int& y, const table& maze);
//Знайти вихід з лабіринту
template <typename table>
bool MazeWayOut(table& maze, unsigned int point_r, unsigned int point_c);
//Вивести лабіринт із знайденим шляхом
template <typename table>
void PrintMazeWayOut(table& maze);
int main()
{
const int rows = 8; //довжина лабіринту
const int cols = 8; //ширина лабіринту
unsigned int point_r = 0;
unsigned int point_c = 0;
int maze[rows][cols] = { 0 }; //лабіринт
if (ReadMaze("d:\\map.txt", maze))
{
if (GetXY(point_r, point_c, maze))
{
if(MazeWayOut(maze, point_r, point_c))
PrintMazeWayOut(maze);
}
}
return 0;
}
Потім користуючись пошуком знаходимо:
Алгоритм розв'язування лабіринтів
https://uk.wikipedia.org/wiki/%D0%90%D0 … 1%96%D0%B2
В цій реалізації використовується два додаткових масиви для відвіданих точок і знайденого шляху
Я вирішив їх не використовувати і модифікувати значення в заданому лабіринті
Так само знаходимо, як отримати число з клавіатури?
Як прочитати текстовий файл?
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
//прочитати дані про лабіринт з текстового файлу
template <typename table>
bool ReadMaze(const std::string& fullPath, table& maze);
//отримати координати від користувача
template <typename table>
bool GetXY(unsigned int& x, unsigned int& y, const table& maze);
//Знайти вихід з лабіринту
template <typename table>
bool MazeWayOut(table& maze, unsigned int point_r, unsigned int point_c);
//Вивести лабіринт із знайденим шляхом
template <typename table>
void PrintMazeWayOut(table& maze);
int main()
{
const int rows = 8; //довжина лабіринту, в завданні 6
const int cols = 8; //ширина лабіринту, в завданні 6
unsigned int point_r = 0;
unsigned int point_c = 0;
int maze[rows][cols] = { 0 }; //лабіринт
if (ReadMaze("d:\\map.txt", maze))
{
if (GetXY(point_r, point_c, maze))
{
if(MazeWayOut(maze, point_r, point_c))
PrintMazeWayOut(maze);
}
}
return 0;
}
template <typename table>
bool ReadMaze(const std::string& fullPath, table& maze)
{
bool result = true;
const int rows = sizeof(maze) / sizeof(maze[0]);
const int cols = sizeof(maze[0]) / sizeof(maze[0][0]);
unsigned int x = 0;
unsigned int y = 0;
std::string line;
ifstream mazeFile(fullPath);
if (mazeFile.is_open())
{
while (getline(mazeFile, line))
{
std::cout << line << std::endl;
x = 0;
for (size_t i = 0; i < line.length(); i++)
{
if (line[i] == '0')
{
maze[y][x] = 0;
x++;
}
else if (line[i] == '1')
{
maze[y][x] = 1;
x++;
}
else if (line[i] == '9')
{
maze[y][x] = 9;
x++;
}
if (x >= cols)
break;
}
y++;
if (y >= rows)
break;
}
std::cout << std::endl;
mazeFile.close();
}
else
{
std::cout << "Unable to open file" << std::endl;
result = false;
}
return result;
}
template <typename table>
bool GetXY(unsigned int& x, unsigned int& y, const table& maze)
{
bool result = false;
const int rows = sizeof(maze) / sizeof(maze[0]);
const int cols = sizeof(maze[0]) / sizeof(maze[0][0]);
//тут має бути введення з клавіатури
x = 1;
y = 1;
//перевірка вводу
if (x < rows && y < cols && maze[y][x] != 1) //1 - стіна
{
result = true;
std::cout << "Start point x = " << x << ", y = " << y << std::endl;
std::cout << std::endl;
}
else
{
std::cout << "Wrong point" << std::endl;
}
return result;
}
//2 - відвідана точка
//3 - знайдений шлях
template <typename table>
bool MazeWayOut(table& maze, unsigned int point_r, unsigned int point_c)
{
const int rows = sizeof(maze) / sizeof(maze[0]);
const int cols = sizeof(maze[0]) / sizeof(maze[0][0]);
if (maze[point_c][point_r] == 9)
{
maze[point_c][point_r] = 3;
return true;
}
if (maze[point_c][point_r] == 1 || maze[point_c][point_r] >= 2)
return false;
if(!maze[point_c][point_r])
maze[point_c][point_r] = 2;
if(point_r != 0)
{
if (MazeWayOut(maze, point_r - 1, point_c)) {
maze[point_c][point_r] = 3;
return true;
}
}
if (point_r < (rows - 1))
{
if (MazeWayOut(maze, point_r + 1, point_c)) {
maze[point_c][point_r] = 3;
return true;
}
}
if (point_c != 0)
{
if (MazeWayOut(maze, point_r, point_c - 1)) {
maze[point_c][point_r] = 3;
return true;
}
}
if (point_c < (cols - 1))
{
if (MazeWayOut(maze, point_r, point_c + 1)) {
maze[point_c][point_r] = 3;
return true;
}
}
return false;
}
template <typename table>
void PrintMazeWayOut(table& maze)
{
const int rows = sizeof(maze) / sizeof(maze[0]);
const int cols = sizeof(maze[0]) / sizeof(maze[0][0]);
for (int y = 0; y < cols; y++)
{
for (int x = 0; x < rows; x++)
{
if (maze[y][x] == 2)//просто відвідані точки
maze[y][x] = 0;
std::cout << maze[y][x] << " ";
}
std::cout << endl;
}
}
Для лабіринту
1 1 1 1 1 1 1 1
1 0 0 1 0 1 0 1
1 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1
1 0 1 0 0 1 1 1
1 1 1 1 0 0 0 1
1 9 0 0 0 1 1 1
1 1 1 1 1 1 1 1
і точки (1,1)
знайдено шлях
1 1 1 1 1 1 1 1
1 3 3 1 0 1 0 1
1 1 3 3 3 1 0 1
1 0 0 1 3 0 0 1
1 0 1 0 3 1 1 1
1 1 1 1 3 0 0 1
1 9 3 3 3 1 1 1
1 1 1 1 1 1 1 1
