BG Development


  Reply to this topicStart new topicStart Poll

> 
my_shadow
: 09-11-2019, 04:33
Quote Post



:
:
:

: 597
: 07.09.07



- . - X e , Y . ?

CODE

#include <iostream>
using namespace std;

const int _INIT_X = 12;
const int _INIT_Y = 12;
const char _INIT[_INIT_X][_INIT_Y] {
{'#','#','#','#','#','#','#','#','#','#','#','#'},
{'#',' ',' ',' ','#',' ',' ',' ',' ',' ',' ','#'},
{'B',' ','#',' ','#',' ','#','#','#','#',' ','#'},
{'#','#','#',' ',' ',' ',' ',' ',' ','#',' ','#'},
{'#',' ',' ',' ',' ','#','#','#',' ','#',' ','#'},
{'#','#','#','#',' ','#',' ','#',' ','#',' ','#'},
{'#',' ',' ','#',' ','#',' ','#',' ','#',' ','#'},
{'#','#',' ','#',' ','#',' ','#',' ','#',' ','#'},
{'#',' ',' ',' ',' ',' ',' ',' ',' ','#',' ','#'},
{'#','#','#','#','#','#',' ','#','#','#',' ','#'},
{'#',' ',' ',' ',' ',' ',' ','#',' ',' ',' ','#'},
{'#','#','#','#','#','#','#','#','#','E','#','#'},
};

class Maze {
public:
static const int max_x = 64;
static const int max_y = 64;

Maze();
void plotMap();
void solve();
private:
char map[max_x][max_y];
int dimX;
int dimY;
int startX;
int startY;

void loadDefault();
void findPath(int x, int y);
};

Maze::Maze() {
loadDefault();
}

void Maze::plotMap() {
cout << endl;
for(int x = 0; x < dimX; ++x) {
for(int y = 0; y < dimY; ++y) {
if(map[x][y] == ' ') {
cout << "\033[43m" << ' ' << "\033[0m";
}
else if(map[x][y] == '#') {
cout << "\033[41m" << ' ' << "\033[0m";
}
else if(map[x][y] == 'B') {
cout << 'B';
}
else if(map[x][y] == 'E') {
cout << 'E';
}
else if(map[x][y] == '*') {
// visited cell
cout << "\033[43m" << '*' << "\033[0m";
} else {
// uncnown symbol
cout << "?";
}
}
cout << endl;
}
cout << endl;
}

void Maze::loadDefault() {
if(max_x < _INIT_X || max_y < _INIT_Y) {
cerr << "Initial matrix is too large\n";
abort();
}
dimX = _INIT_X;
dimY = _INIT_Y;
for(int x = 0; x < dimX; ++x) {
for(int y = 0; y < dimY; ++y) {
map[x][y] = _INIT[x][y];
if(map[x][y] == 'B') {
startX = x;
startY = y;
}
}
}
}

void Maze::solve() {
findPath(startX, startY);
}

void Maze::findPath(int x, int y) {
// base cases
if(x < 0 || x >= dimX) return;
if(y < 0 || y >= dimY) return;
// we founds exit
if(map[x][y] == 'E') {
plotMap();
return;
}
// cell is not free
if(map[x][y] != ' ' && map[x][y] != 'B') return;

// mark the cell as visited
map[x][y] = '*';
// recursive find
findPath(x, y + 1); // up
findPath(x, y - 1); // down
findPath(x - 1, y); // left
findPath(x + 1, y); // right
// unmark cell
map[x][y] = ' ';
}

int main() {
Maze m;
m.solve();
}


my_shadow 09-11-2019, 04:41
PMEmail Poster
Top
: 09-11-2019, 07:34
Quote Post



:
:
:

: 8483
: 11.11.06



, , , "". , "".

09-11-2019, 07:37
PM
Top
thrawn
: 09-11-2019, 08:51
Quote Post



:
:
:

: 2607
: 17.01.17



- . , .

thrawn 09-11-2019, 08:52
PMEmail Poster
Top
: 09-11-2019, 09:39
Quote Post



:
:
:

: 8483
: 11.11.06



QUOTE (thrawn @ 09-11-2019, 08:51)
- . , .

? , . ,
PM
Top
thrawn
: 09-11-2019, 09:51
Quote Post



:
:
:

: 2607
: 17.01.17



.
PMEmail Poster
Top
: 09-11-2019, 10:24
Quote Post



:
:
:

: 8483
: 11.11.06



PM
Top
SuN
: 09-11-2019, 11:25
Quote Post


Group Icon
:
:
:

: 9520
: 27.01.05



. (, ) . . icon_smile.gif

SuN 09-11-2019, 11:26


--------------------
.
, .
PMEmail Poster
Top
thrawn
: 09-11-2019, 13:16
Quote Post



:
:
:

: 2607
: 17.01.17



,
CODE
public class Test {
   private static char maze[][] = new char[][]{
       {'#','#','#','#','#','#','#','#','#','#','#','#'},
       {'#',' ',' ',' ','#',' ',' ',' ',' ',' ',' ','#'},
       {'B',' ','#',' ','#',' ','#','#','#','#',' ','#'},
       {'#','#','#',' ',' ',' ',' ',' ',' ','#',' ','#'},
       {'#',' ',' ',' ',' ','#','#','#',' ','#',' ','#'},
       {'#','#','#','#',' ','#',' ','#',' ','#',' ','#'},
       {'#',' ',' ','#',' ','#',' ','#',' ','#',' ','#'},
       {'#','#',' ','#',' ','#',' ','#',' ','#',' ','#'},
       {'#',' ',' ',' ',' ',' ',' ',' ',' ','#',' ','#'},
       {'#','#','#','#','#','#',' ','#','#','#',' ','#'},
       {'#',' ',' ',' ',' ',' ',' ','#',' ',' ',' ','#'},
       {'#','#','#','#','#','#','#','#','#','E','#','#'},
   };

   private static void print() {
       for(int y = 0; y < maze.length; y++) {
           for (int x = 0; x < maze[y].length; x++) {
               System.out.print(maze[y][x]);
           }
           System.out.println();
       }
   }

   private static boolean forward(int x, int y) {
       int maxX = maze[y].length;
       int maxY = maze.length;

       if(x < 0 || x > maxX) return false;
       if(y < 0 || y > maxY) return false;

       boolean free =  maze[y][x] != 'B' && maze[y][x] != '#' && maze[y][x] != 'X' && maze[y][x] != '*';
       if(free) {
           System.out.println(String.format("X = %d, Y = %d", x, y));
       }

       return free;
   }

   private static void clear(int x, int y) {
       int maxX = maze[y].length;
       int maxY = maze.length;

       if(x < 0 || x > maxX) return;
       if(y < 0 || y > maxY) return;

       if(maze[y][x] == '*') maze[y][x] = ' ';
   }

   public static void main(String[] args) {
       int x = 0;
       int y = 2;

       System.out.println(String.format(" X = %d, Y = %d", x, y));
       while (true) {
           if(maze[y][x] == 'E') {
               System.out.println("...");
               return;
           }

           if (forward(x + 1, y)) x++;
           else if (forward(x, y + 1)) y++;
           else if (forward(x - 1, y)) x--;
           else if (forward(x, y - 1)) y--;
           else {
               maze[y][x] = 'X';

               clear(x + 1, y);
               clear(x, y + 1);
               clear(x - 1, y);
               clear(x, y - 1);

               continue;
           }

           if(maze[y][x] == 'E') {
               System.out.println("...");
               return;
           }

           maze[y][x] = '*';
       }
   }
}
PMEmail Poster
Top
1 (1 , 0 )
, :
« | C/C++ | »

Topic Options Reply to this topicStart new topicStart Poll

 


Copyright © 2003-2019 | BG Development | All Rights Reserved
RSS 2.0