I was writing the program for finding a path through an defined matrix.
#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();
}
This program works fine for most of the inputs. But gives an address boundry error for the following input
Enter rows and colums: 4 4
ENter initial configuration (1 for block, 0 for open):0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0
Enter initial state in row column:1 0
Enter final state in row column:3 3 fish: “./a.out” terminated by signal SIGSEGV (Address boundary error)
Please suggest the possible reason for this error and how to correct it
I realized where the mistake was. I did not initialize x and y in the functions maze::up(), maze::down(), maze::right() and maze::left() as it was always supposed to be initialized by the function while traversing the matrix. The Error was in the algorithm itself. The variable curr from state_search() was supposed to denote the depth of the BFS tree. But since it was incrementing for every node found, it denoted the depth wrongly causing error whenever there were 2 possible paths.
To solve this issue, I removed the curr variable from state_search() and added it to the class definition initializing it to 1 and incrementing it whenever the functions maze::up(), maze::down(), maze::right() and maze::left() are called.
here is the complete working code
#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();
}