The following grid of ones and zeroes is a double scripted array representation
ID: 3697434 • Letter: T
Question
The following grid of ones and zeroes is a double scripted array representation of a terrain of size 12 x 12.
111111111111
100010000101
001010000101
110010000101
100000110100
111100110101
101100110101
111100110101
100000000101
111110000101
100000000101
111111111111
The ones represent the obstacles if the field, and the zeroes represent positions in the possible path through the field. In this assignment, the field will have a single entrance and a single exit, i.e., there will be only two zeroes in the “outer wall” of the field. In order to find the entrance and the exit, traverse the outer wall of the field in the clockwise direction, starting from the upper left corner. The first encountered zero will be the entrance (square [4,11] in the field above), and next zero will be the exit (square [2,0]). In this assignment, the size of a field is NOT FIXED. Each array dimension will vary in size between 5 and 100. There are several simple algorithms for walking through a field that guarantee finding the path, if one exists. The only legal moves are north, west, south or east (no diagonal moves). For example, look to your right and walk forward. Always keep the obstacle to your right. If you reach the corner of the obstacle, turn right and continue following its “border” on your right side. There may be a shorter path than the one you have taken, but in this way you are guaranteed to get out of the field. In this algorithm, if you exit from the field through the entrance, this means that the path from the entrance to the exit does not exist. Otherwise, the algorithm has found a path that avoids all obstacles. In your assignment, you need to write a program called path.c. First of all, the program should ask user to type in the size of the field (if you enter 12, 6, this will imply a 12 rows and 6 columns field). Then the program should request the user to type in the name of the input file that contains the field (the code for reading the file is offered to you on Moodle). You may assume that the field size given to the program always matches the size in the file. The field will be given to your program in an ASCII text file, looking very much like the one above (but of proper size). Upon opening the file, your program must find the entrance. As your program attempts to find a path through the field, it should place the character X into each square visited in the path. Note that your program MUST NOT replace a 1 (an obstacle) with an X. Only zeroes can be replaced by X. Before exiting, your program must display the field with the traversed path, that is, the path between the entrance and the exit (the path is marked by X). Your program must also report whether the path was found or not. In case of the field from the figure above, the path could not be found and your program would provide the following output: 111111111111 1000100001X1 0010100001X1 1100100001X1 1000001101XX 1111001101X1 1011001101X1 1111001101X1 1000000001X1 1111100001X1 1000000001X1 111111111111 No path found. I need help doing this in C or C++.
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define north 0
#define west 1
#define south 2
#define east 3
int main(int argc,char *argv[])
{
int rows,columns,grid[100][100],j;
char name[20];
printf(" Please Type in the size of the field:");
scanf("%d %d",&rows,&columns);
printf(" The rows are %d and the columns are %d",rows,columns);
printf(" Please type in the name of the input file that contains the field ");
scanf("%s",name);
rows=12;
columns=12;
strcpy(name,"path");
strcat(name,".txt");
printf(" The name is %s ",name);
FILE *fp;
fp=fopen(name,"r");
if(fp==NULL)
exit(EXIT_FAILURE);
char c;
int row=0;col=0,i;
while (feof(fp)==0)
{
c=fgetc(fp);
if((c=='1') || (c=='0'))
{
if(c=='1')
grid[row][col]=1;
if(c=='0')
grid[row][col]=0;
col=col+1;
if(col==columns)
{
col=0;
row=row+1;
}
}
}
for(j=0;j<rows;j++)
{
printf(" ");
for(i=0;i<columns;i++)
printf("%d",grid[j][i]);
}
int posx,posy,direction=east,flag_end=0,flag_entry=0,flag_exit=0;
int entry,entrx,exity,exitx;
posx=0;
posy=0;
while(flag_exit==0 &&flag_end==0)
{
switch (direction)
{
case east:
{
if(posx<columns-1)
posx=posx+1;
else
{
posy=posy+1;
direction=south;
}
break;
}
case south:
{
if(posy<rows-1)
posy=posy+1;
else
{
posx=posx-1;
direction=west;
}
break;
}
case west:
{
if(posx!=0)
posx=posx-1;
else
{
posy=posy-1;
direction=north;
}
break;
}
case north:
{
if(posy!=0)
posy=posy-1;
else
flag_end=1;
break;
}
}
if(grid[posy][posx]==0)
{
if(flag_entry==1)
{
flag_exit=1;
printf(" we have an exit ");
exity=posy;
exitx=posx;
}
else
{
flag_entry=1;
printf(" we have an entry ");
entry=posy;
entrx=posx;
}
}
}
fclose (fp);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.