The following grid of ones and zeroes is a double scripted array representation
ID: 3667559 • Letter: T
Question
The following grid of ones and zeroes is a double scripted array representation of a terrain of size 12 x 12.
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 0 0 0 1 0 1
0 0 1 0 1 0 0 0 0 1 0 1
1 1 0 0 1 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1 0 0
1 1 1 1 0 0 1 1 0 1 0 1
1 0 1 1 0 0 1 1 0 1 0 1
1 1 1 1 0 0 1 1 0 1 0 1
1 0 0 0 0 0 0 0 0 1 0 1
1 1 1 1 1 0 0 0 0 1 0 1
1 0 0 0 0 0 0 0 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1
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. 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:
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 0 0 0 1 X 1
0 0 1 0 1 0 0 0 0 1 X 1
1 1 0 0 1 0 0 0 0 1 X 1
1 0 0 0 0 0 1 1 0 1 X X
1 1 1 1 0 0 1 1 0 1 X 1
1 0 1 1 0 0 1 1 0 1 X 1
1 1 1 1 0 0 1 1 0 1 X 1
1 0 0 0 0 0 0 0 0 1 X 1
1 1 1 1 1 0 0 0 0 1 X 1
1 0 0 0 0 0 0 0 0 1 X 1
1 1 1 1 1 1 1 1 1 1 1 1
No Path Found.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define north 0
#define west 1
#define south 2
#define east 3
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char *argv[]) {
int rows, columns, grid[100][100], j;
char name[20];
/* Ask the user
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);
/* don't ask the user */
rows=12;
columns=12;
strcpy(name,"path");
//prepare to open
strcat(name,".txt");
printf(" The name is %s ", name);
// opening the file
FILE *fp;
fp = fopen(name,"r");
if (fp == NULL)
exit(EXIT_FAILURE);
/* reading the file */
char c;
int row=0,col=0,i;
while (feof(fp) == 0)
{
c = fgetc(fp);
//printf("%c",c);
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;
}
}
}
/* PRINTING THE FILE */
for (j=0; j<rows;j++)
{
printf(" ");
for (i=0;i<columns;i++)
printf("%d",grid[j][i]);
}
/*search the entry and exit*/
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;
}
//printf(" the entry is not the position %d %d ", posx,posy);
break;
}
case south:
{
if (posy<rows-1)
posy=posy+1;
else
{
posx=posx-1;
direction=west;
}
//printf(" the entry is not the position %d %d ", posx,posy);
break;
}
case west:
{
if (posx!=0)
posx=posx-1;
else
{posy=posy-1;
direction=north;
}
//printf(" the entry is not the position %d %d ", posx,posy);
break;
}
case north:
{
if (posy!=0)
posy=posy-1;
else
flag_end=1;
//printf(" the entry is not the position %d %d ", posx,posy);
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;
}
}
}
//printf(" the entry is the position %d %d", entry, entrx);
//printf(" the exit is the position %d %d", exity, exitx);
/* closing the file */
fclose ( fp );
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.