Создать программу, отыскивающую проход по лабиринту!!!

[Сtrl]

Сообщение от Protected_fat

А как задать структуру для матрицы? как реализовать стек для матрицы? я не совсем понимаю...

typedef vector< vector<bool> > maze_t;

И теперь maze_t - это тип лабиринта. Создавать переменные знаешь как, надеюсь?

maze_t maze1; //переменная maze1 - лабиринт

[Protected_fat]

#include <vector>
#include <map>
#include <iostream>
#include <stdlib.h>
#include <conio.h>
using namespace std;

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()
    int matrix_t[10][10];
    int i, j;
    FILE *f1;
    f1 = fopen("matrix.txt", "r");
    for (i=1; i<=10; i++){
    for (j=1; j<=10; j++) 
    fscanf(f1,"%d",&matrix_t[i][j]);}
    fclose ( f1 );
     printf("Labirint A\n"); 
   for (i=1; i<=10; i++) {      
   for (j=1; j<=10; j++)     
   printf ( "%3d", matrix_t[i][j] );  
   printf("\n");} 
   printf("\n");
    find(matrix_t[10][10]);
                
    getch();
    return 0;
}

___________
Код нужно оформлять по правилам:
тегом [CODE]..[/СODE] (это кнопочка с решёточкой #)
Не забывайте об этом!
Модератор.

[Protected_fat]

вот я кое-что нашла... и пыталась main доделать, но знаю... что-то там не так...
ничего не работает...
и ошибки выдает еще до main'а...

[Protected_fat]

typedef std :: vector<std :: vector<bool>> matrix_t;

вот в этой строчке ошибка...

[Protected_fat]

ох... я еще похоже си с c++ перемешала...
блин...

[Protected_fat]

Помогите исправить и разобраться пожалуйста

[eoln]

Сообщение от Protected_fat

1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 0 1 0 0 0 1 1
1 1 1 0 0 0 1 0 1 1
1 0 1 1 1 0 0 0 1 1
1 0 0 0 0 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 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
По единичкам ходить можно, а нолики - это стена.
Нужно задать начало и конец...и найти путь...

Точно нолики - это стена? Может наоборот? Ибо по такому алгоритму у меня выдало 1 601 472 вариантов прохода по лабиринту (это влючая петляния без пересечений).
Выдернул старые наработки, без стека - просто рекурсия с копированием нужных подпутей, выводит всевозможные непересекающиеся пути
x, y - вход, X, Y -выход, 0-коридор, 1-стена

int mas[10][10]={
 1,1,0,1,1,1,1,1,1,1
,1,1,0,1,1,1,1,1,1,1
,1,1,0,0,1,0,0,0,1,1
,1,1,1,0,0,0,1,0,1,1
,1,0,1,1,1,0,0,0,1,1
,1,0,0,0,0,0,1,1,1,1
,1,1,1,1,1,0,1,1,1,1
,1,1,1,1,1,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};

int X=5, Y=1, x=2, y=2;

int MakeList(int x, int y, char s[1000])
{
    char st[1000];
    strcpy(st,s);
    sprintf (st, "%s[%d,%d] -> ", st, x, y);
    if (x==X && y==Y)
    {
        printf("%s\n\n",st);
        return 0;
    }
    if (x > 0) if (mas[x - 1][y] == 0) {mas[x][y]+=3; MakeList(x-1, y, st); mas[x][y]-=3;}
    if (x < 9) if (mas[x + 1][y] == 0) {mas[x][y]+=3; MakeList(x+1, y, st); mas[x][y]-=3;}
    if (y > 0) if (mas[x][y - 1] == 0) {mas[x][y]+=3; MakeList(x, y-1, st); mas[x][y]-=3;}
    if (y < 9) if (mas[x][y + 1] == 0) {mas[x][y]+=3; MakeList(x, y+1, st); mas[x][y]-=3;}
}

int main()
{
    MakeList(x, y, "");
    return 0;
}

P.S. +=3/-=3 - запирает/отпирает клетки при итерациях, сюда также можно добавить pop/push для стека

[Protected_fat]

[2,2] -> [2,3] -> [3,3] -> [3,4] -> [3,5] -> [2,5] -> [2,6] -> [2,7] -> [3,7] ->
[4,7] -> [4,6] -> [4,5] -> [5,5] -> [5,4] -> [5,3] -> [5,2] -> [5,1] ->

[2,2] -> [2,3] -> [3,3] -> [3,4] -> [3,5] -> [4,5] -> [5,5] -> [5,4] -> [5,3] ->
[5,2] -> [5,1] ->

вот, что мне выдает после запуска...
он и по 1, и по 0 ходит

[Protected_fat]

помогите доделать пожалуйста!!!

 /************************************/
 /* Нахождение выхода из  лабиринта */           
/**********************************/
#include <iostream>
#include <stdlib.h>
#include <conio.h>
using namespace std;

struct Node {
   int* k = new int[2];
   Node* p;
   
};
Node * first(int d, int c){
    Node *pv=new Node;
    int* temp=new int[2];
    temp[0]=d;
    temp[1]=c;
    pv->k = temp;
    pv->p = 0;
    delete temp;
    return pv;
}

void push(Node **top, int d, int c){
     Node *pv = new Node;
     int* temp=new int[2];
     temp[0]=d;
     temp[1]=c;
     pv->k = temp;
     pv->p = *top;
     *top = pv;
     delete temp;
}

int* pop(Node **top){ 
     int* temp = (*top)->k;
     Node *pv = *top;
     *top = (*top)->p;
     delete pv;
     return temp;
}

int main()
{
    int A[10][10] = {1,1,0,1,1,1,1,1,1,1
                    ,1,1,0,1,1,1,1,1,1,1
                    ,1,1,0,0,1,0,0,0,1,1
                    ,1,1,1,0,0,0,1,0,1,1
                    ,1,0,1,1,1,0,0,0,1,1
                    ,1,0,0,0,0,0,1,1,1,1
                    ,1,1,1,1,1,0,1,1,1,1
                    ,1,1,1,1,1,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};
  int i=1, j=3; 
  int koni=8, konj=8;
  Node *top = first(i,j);
  
 while(i!=koni && j!=konj){
     if(i+1<10 && A[i+1][j]==0){ push(*top,i+1,j); }
     if(j+1<10 && A[i][j+1]==0) {push(*top,i,j+1);}
     if(j-1>0 && A[i][j-1]==0){ push(*top,i,j-1);}
     if(i-1>0 && A[i-1][j]==0){ push(*top,i-1,j);}           
 }
    getch();
    return 0;}

[Protected_fat]

еще ошибку вот здесь выдает int* k = new int[2];
не понимаю, как надо...