Skip to content

Instantly share code, notes, and snippets.

@friendleemachine
Created October 22, 2018 15:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save friendleemachine/490d1b78ad9ee5aee72569075ac52440 to your computer and use it in GitHub Desktop.
Save friendleemachine/490d1b78ad9ee5aee72569075ac52440 to your computer and use it in GitHub Desktop.
Maze solver
#include <iostream>
#include <fstream>
#include <string>
class Maze {
private:
int R, C, sR, sC, eR, eC;
std::string data;
public:
Maze(std::string filepath) {
try {
std::ifstream fin(filepath);
if (!fin) {
throw 1;
}
std::string s;
fin >> s;
this->C = s.length();
std::string data = s;
this->R = 1;
while (fin >> s) {
data += s;
this->R++;
}
this->data = data;
int pos = data.find("S");
this->sC = pos % C;
this->sR = pos / C;
this->data[pos]='_'; //необходимо для работы Solve
pos = data.find("E");
this->eC = pos % C;
this->eR = pos / C;
this->data[pos]='_';
fin.close();
}
catch(int i) {
std::cout << "Error " << 1 <<": can't open file" << "\n"; //если не получилось открыть файл
}
}
char map(int x, int y) { //метод нужен для обращения по координатам
if (y * this->C - 1 + x > data.length()) {
return '#';
}
else {
return data[y * this->C + x];
}
}
bool Solve() {
return Solve(this->sC, this->sR);
}
bool Solve(int x, int y) {
data[y * this->C + x] = '*';
if (x == this->eC && y == this->eR) {
return true;
}
if (x > 0 && map(x - 1, y) == '_' && Solve(x - 1, y)) {
return true;
}
if (x < C && map(x + 1, y) == '_' && Solve(x + 1, y)) {
return true;
}
if (y > 0 && map(x, y - 1) == '_' && Solve(x, y - 1)) {
return true;
}
if (y < R && map(x, y + 1) == '_' && Solve(x, y + 1)) {
return true;
}
data[y * this->C + x] = '_';
return false;
}
friend std::ostream& operator<<(std::ostream& os, const Maze& mz);
};
std::ostream& operator<<(std::ostream& os, const Maze& mz) {
for (int i = 0; i < mz.R; i++) {
for (int j = 0; j < mz.C; j++) {
if (j == 0 && i != 0) {
os << "\n";
}
os << mz.data[i * mz.C + j];
}
}
return os;
}
int main () {
std::string filepath = "maze"; //путь до файла с лабиринтом
std::ofstream fout("solved"); //путь до файла куда надо вывести решение
Maze filemaze(filepath);
if (filemaze.Solve()) {
fout << filemaze;
}
else {
fout << "Can't find the path" << "\n"; //если нет пути
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment