Created
October 22, 2018 15:38
-
-
Save friendleemachine/490d1b78ad9ee5aee72569075ac52440 to your computer and use it in GitHub Desktop.
Maze solver
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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