Implement remaining function. Everything else is provided. Use given material to
ID: 3550746 • Letter: I
Question
Implement remaining function. Everything else is provided. Use given material to receive points. Need the build function. Use Recursion!!!
#include "stdio.h"
#define SIZE 10
struct cell_type {
int row;
int col;
int dir;
};
typedef struct cell_type Cell;
Cell sol[SIZE*SIZE];
int maze[SIZE][SIZE] = {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 1, 1, 0, 0, 0, 1,
1, 0, 1, 0, 0, 1, 0, 1, 0, 1,
1, 0, 1, 1, 0, 0, 0, 1, 0, 1,
1, 0, 0, 1, 1, 1, 1, 0, 0, 1,
1, 1, 0, 0, 0, 0, 1, 0, 1, 1,
1, 0, 0, 1, 1, 0, 0, 0, 0, 1,
1, 0, 1, 0, 0, 0, 0, 1, 1, 1,
1, 0, 0, 0, 1, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};
void build(int);
void printSolution(int);
int cellOk(int);
int getNextCell(int);
void main(void)
{
sol[0].row = 1;
sol[0].col = 1;
sol[0].dir = 0;
build(0);
}
void build(int n)
{
//Implement this
}
void printSolution(int n)
{
int i;
printf(" A solution was found at: ");
for (i = 0; i <= n; i++)
printf("(%d, %d) ", sol[i].row, sol[i].col);
printf(" ");
}
int getNextCell(int n)
{
sol[n + 1].row = sol[n].row;
sol[n + 1].col = sol[n].col;
sol[n + 1].dir = 0;
switch (sol[n].dir) {
case 0:
sol[n].dir = 'e';
sol[n + 1].col++;
return 1;
case 'e':
sol[n].dir = 's';
sol[n + 1].row++;
return 1;
case 's':
sol[n].dir = 'w';
sol[n + 1].col--;
return 1;
case 'w':
sol[n].dir = 'n';
sol[n + 1].row--;
return 1;
case 'n':
return 0;
}
return 0;
}
int cellOk(int n)
{
int i;
if (maze[sol[n + 1].row][sol[n + 1].col])
return 0;
for (i = 0; i<n; i++)
if (sol[n + 1].row == sol[i].row && sol[n + 1].col ==
sol[i].col)
return 0;
return 1;
}
Explanation / Answer
sourcecode and output when executed: http://ideone.com/eq03sN
#include "stdio.h"
#define SIZE 10
struct cell_type {
int row;
int col;
int dir;
};
typedef struct cell_type Cell;
Cell sol[SIZE*SIZE];
int maze[SIZE][SIZE] = {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 1, 1, 0, 0, 0, 1,
1, 0, 1, 0, 0, 1, 0, 1, 0, 1,
1, 0, 1, 1, 0, 0, 0, 1, 0, 1,
1, 0, 0, 1, 1, 1, 1, 0, 0, 1,
1, 1, 0, 0, 0, 0, 1, 0, 1, 1,
1, 0, 0, 1, 1, 0, 0, 0, 0, 1,
1, 0, 1, 0, 0, 0, 0, 1, 1, 1,
1, 0, 0, 0, 1, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};
void build(int);
void printSolution(int);
int cellOk(int);
int getNextCell(int);
void main(void)
{
sol[0].row = 1;
sol[0].col = 1;
sol[0].dir = 0;
build(0);
}
void build(int n)
{
if((sol[n].row == SIZE-2)&&(sol[n].col == SIZE-2))
{
printSolution(n);
}
else
{
while(getNextCell(n))
{
if(cellOk(n)) build(n+1);
}
}
}
void printSolution(int n)
{
int i;
printf(" A solution was found at: ");
for (i = 0; i <= n; i++)
printf("(%d, %d) ", sol[i].row, sol[i].col);
printf(" ");
}
int getNextCell(int n)
{
sol[n + 1].row = sol[n].row;
sol[n + 1].col = sol[n].col;
sol[n + 1].dir = 0;
switch (sol[n].dir) {
case 0:
sol[n].dir = 'e';
sol[n + 1].col++;
return 1;
case 'e':
sol[n].dir = 's';
sol[n + 1].row++;
return 1;
case 's':
sol[n].dir = 'w';
sol[n + 1].col--;
return 1;
case 'w':
sol[n].dir = 'n';
sol[n + 1].row--;
return 1;
case 'n':
return 0;
}
return 0;
}
int cellOk(int n)
{
int i;
if (maze[sol[n + 1].row][sol[n + 1].col])
return 0;
for (i = 0; i<n; i++)
if (sol[n + 1].row == sol[i].row && sol[n + 1].col == sol[i].col)
return 0;
return 1;
}