list — Ошибка ограничения адреса при использовании STL в переполнении стека

Question

list — Ошибка ограничения адреса при использовании STL в переполнении стека

Я писал программу для поиска пути по определенной матрице.

#include<iostream>
#include<list>

using namespace std;

class maze{
int inst[10][10];
int m,n,initr,initc,finalr,finalc;
public:
maze(int c){
if(c==1) return;
cout<<"\n Enter rows and colums: ";
cin>>m>>n;
cout<<endl<<"\n ENter initial configuration (1 for block, 0 for open):";
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>inst[i][j];
}
}
cout<<endl<<"Enter initial state in row column:";
cin>>initr>>initc;
cout<<endl<<"Enter final state in row column:";
cin>>finalr>>finalc;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==1) inst[i][j]=(-1);
}
}
inst[initr][initc]=1;
}
bool up(int curr){
int x,y;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==curr) {
x=i;
y=j;
break;
}
}
}
if(x==0) return false;
if(inst[x-1][y]==0){
//cout<<"\n up "<<x-1<<y;
inst[x-1][y]=curr+1;
return true;
}else return false;

}
bool down(int curr){
int x,y;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==curr) {
x=i;
y=j;
break;
}
}
}
if(x==m-1) return false;
if(inst[x+1][y]==0){
//cout<<"\n down "<<x+1<<y;
inst[x+1][y]=curr+1;
return true;
}else return false;

}
bool left(int curr){
int x,y;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==curr) {
x=i;
y=j;
break;
}
}
}
if(y==0) return false;
if(inst[x][y-1]==0){
//cout<<"\n left "<<x<<y-1;
inst[x][y-1]=curr+1;
return true;
}else return false;

}
bool right(int curr){
int x,y;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==curr) {
x=i;
y=j;
break;
}
}
}

if(y==n-1) return false;
if(inst[x][y+1]==0){
//cout<<"\n right "<<x<<y+1;
inst[x][y+1]=curr+1;
return true;
}else return false;

}
bool check(int curr){
int x,y;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==curr) {
x=i;
y=j;
break;
}
}
}
if(x==finalr && y==finalc) return true;
else return false;
}
void print_maze(){
cout<<endl<<endl;
for(int i=0;i<m;i++){
cout<<endl;
for(int j=0;j<n;j++){
cout<<"\t"<<inst[i][j];
}
}
}

};

bool state_search(){
int curr=1;
maze start(0),temp(1);
list<maze> queue;

queue.push_back(start);
while(!queue.empty()){
start = queue.front();
queue.pop_front();
if(start.check(curr)){
start.print_maze();
return true;
}
//start.print_maze();

temp=start;
if(temp.up(curr)) queue.push_back(temp);

temp=start;
if(temp.down(curr)) queue.push_back(temp);

temp=start;
if(temp.left(curr)) queue.push_back(temp);

temp=start;
if(temp.right(curr)) queue.push_back(temp);

curr++;
}
cout<<"\n No answer found";
}int main(){
state_search();
}

Эта программа отлично работает для большинства входов. Но выдает ошибку границы адреса для следующего ввода

Введите строки и столбцы: 4 4

ENter Начальная конфигурация (1 для блока, 0 для открытого): 0 0 0 0 0 1 0 1
0 1 1 1 0 0 0 0

Введите начальное состояние в столбце строки: 1 0

Введите конечное состояние в столбце строки: 3 3 рыбы: «./a.out» завершается
сигнал SIGSEGV (ошибка границы адреса)

Пожалуйста, предложите возможную причину этой ошибки и как ее исправить.

0

breadth-first-search c++list runtime-error state-space

Решение

Другие решения

Вы используете неинициализированные переменные x а также y в методе maze::up:

bool up(int curr){
int x,y; // !!!
...

Поэтому, когда в следующих циклах мы не пошли внутрь if Утверждение, что эти переменные по-прежнему содержат мусор из неинициализированной выделенной памяти.

    ...
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==curr) {
x=i;
y=j;
break;
}
}
}
...

И это очень высокая вероятность того, что x не находится в диапазоне [0, 10).

    ...
if(x==0) return false;
if(inst[x-1][y]==0){
...

И мы сразу пытаемся получить значение где-то (inst[x-1][y]) далеко в памяти и завершается ошибкой сегментации.

исправлять: Лучше инициализировать все переменные значимыми значениями. Предположим, что для вашего кода это правильное решение:

bool up(int curr){
int x = 0, y = 0;
...

Вы можете указать компилятору уведомлять вас, когда вы храните где-то неинициализированные переменные.

Если вы используете компилятор GCC, вы можете использовать флаг компиляции:

g++ -O2 -Wuninitialized prog.cpp

И вы увидите много подобных мест в вашем коде.
Дополнительно вы можете использовать флаг -Wallи вы обнаружите, что bool state_search() Функция достигает конца, не возвращая никакого значения.

0

Я понял, где была ошибка. Я не инициализировал x а также y в функциях maze::up(), maze::down(), maze::right() а также maze::left() как это всегда предполагалось инициализировать функцией при обходе матрицы. Ошибка была в самом алгоритме. Переменная curr от state_search() должен был обозначать глубину дерева BFS. Но так как он увеличивался для каждого найденного узла, он обозначал глубину, ошибочно вызывающую ошибку, когда было 2 возможных пути.

Чтобы решить эту проблему, я удалил curr переменная от state_search() и добавил его в определение класса, инициализируя его в 1 и увеличивая его всякий раз, когда функции maze::up(), maze::down(), maze::right() а также maze::left() называются.

вот полный рабочий код

#include<iostream>
#include<list>

using namespace std;

class maze{
int inst[10][10];
int m,n,initr,initc,finalr,finalc,curr;
public:
maze(int c){
if(c==1) return;
cout<<"\n Enter rows and colums: ";
cin>>m>>n;
cout<<endl<<"\n ENter initial configuration (1 for block, 0 for open):";
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>inst[i][j];
}
}
cout<<endl<<"Enter initial state in row column:";
cin>>initr>>initc;
cout<<endl<<"Enter final state in row column:";
cin>>finalr>>finalc;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==1) inst[i][j]=(-1);
}
}
inst[initr][initc]=1;
curr=1;
}
bool up(){
int x=0,y=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==curr) {
x=i;
y=j;
break;
}
}
}
if(x==0) return false;
if(inst[x-1][y]==0){
inst[x-1][y]=curr+1;
curr++;
return true;
}else return false;

}
bool down(){
int x=m-1,y=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==curr) {
x=i;
y=j;
break;
}
}
}
if(x==m-1) return false;
if(inst[x+1][y]==0){
inst[x+1][y]=curr+1;
curr++;
return true;
}else return false;

}
bool left(){
int x,y=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==curr) {
x=i;
y=j;
break;
}
}
}
if(y==0) return false;
if(inst[x][y-1]==0){
inst[x][y-1]=curr+1;
curr++;
return true;
}else return false;

}
bool right(){
int x,y=n-1;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==curr) {
x=i;
y=j;
break;
}
}
}

if(y==n-1) return false;
if(inst[x][y+1]==0){
inst[x][y+1]=curr+1;
curr++;
return true;
}else return false;

}
bool check(){
int x,y;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(inst[i][j]==curr) {
x=i;
y=j;
break;
}
}
}
if(x==finalr && y==finalc) return true;
else return false;
}
void print_maze(){
cout<<endl<<endl;
for(int i=0;i<m;i++){
cout<<endl;
for(int j=0;j<n;j++){
cout<<"\t"<<inst[i][j];
}
}
}

};

bool state_search(){

maze start(0),temp(1);
list<maze> queue;

queue.push_back(start);
while(!queue.empty()){
start = queue.front();
queue.pop_front();
if(start.check()){
start.print_maze();
return true;
}

temp=start;
if(temp.up()) queue.push_back(temp);

temp=start;
if(temp.down()) queue.push_back(temp);

temp=start;
if(temp.left()) queue.push_back(temp);

temp=start;
if(temp.right()) queue.push_back(temp);
}
cout<<"\n No answer found";
return false;
}int main(){
state_search();
}

0

Источник

Accepted Answer

Проблема в том, что вы не инициализируете Икс а также Y значения в ваших функциях вверх, вниз, влево и вправо. И затем, если вы не найдете индексы для curr, вы получите доступ к инст массив случайных индексов.

В право Функция, которую вы должны объявить x и y следующим образом:

int x = 0,y = 0;

В оставил:

int x = m - 1,y = 0;

Сделать то же самое в право а также оставил.

1