inkblot.c

Ink Blotting One method for escaping from a maze is via ‘ink-blotting’. In this method your startin

#include<stdio.h>
#define WALL 9999
#define MAX 10000
#define ARRAY 10
#define LENGH 9

int inkblt(int mz[ARRAY][ARRAY], int x, int y);/*method ink-blotting*/
int east(int mz[ARRAY][ARRAY],int x,int y);/*get the value from east*/
int sorth(int mz[ARRAY][ARRAY],int x, int y);/*get the value from sorth*/
int west(int mz[ARRAY][ARRAY],int x, int y);/*get the value from west*/
int north(int mz[ARRAY][ARRAY],int x, int y);/*get the value from north*/
int display(int mz[ARRAY ][ARRAY]);
int mark(int way[ARRAY ][2], int mark_way[MAX][2],int mz[ARRAY ][ARRAY ],int i,int ex_p[MAX][2]);
/*mark the point can go*/
int copy(int way[ARRAY][2],int mark_way[ARRAY][2]);/*copy ARRY_A to ARRAY_B*/
int calculate_exit(int mz[ARRAY][ARRAY],int x, int y);/*fill the exit way with dot*/
int check_exit(int x,int y);

int main(void){
	int mz[ARRAY ][ARRAY ]={
	9999,9999,9999,9999,9999,9999,9999,9999,9999,9999, 
	9999,0,0,9999,0,0,0,9999,0,0,
	9999,9999,0,9999,0,0,0,9999,0,9999, 
	9999,0,0,0,9999,9999,9999,0,0,9999, 
	9999,9999,9999,0,9999,9999,9999,9999,9999,9999, 
	9999,0,0,0,9999,0,9999,0,9999,9999,
	9999,0,9999,0,0,0,9999,0,0,9999,
	9999,0,9999,9999,9999,0,9999,9999,0,9999,
	9999,9999,0,0,0,0,0,0,0,0,
	9999,9999,0,9999,9999,9999,9999,9999,9999,9999};
	int x,y;
	display(mz);
	printf("please input the start position(X,Y):");
	scanf("%d%d",&y,&x);
	if(inkblt(mz,x,y)==0){
		printf("find the shortest route:\n");
		/*after method ink-blotting,find the shortest route on the maze*/
		display(mz);
	}
	else{
		printf("could not find the way out\n");
		display(mz);
	}
	return 0;
}

int inkblt(int mz[ARRAY][ARRAY], int x, int y){
	int step=1,way[ARRAY][2],mark_way[ARRAY][2],k=1;
	int ex_point[ARRAY][2],exp_x,exp_y;
	if(mz[x][y]==WALL){
		printf("Start is on the WALL\n");
		exit(1);
	}
	mz[x][y]=step;
	way[0][0]=x;
	way[0][1]=y;
	way[1][0]='\0';
	while(k!=0){
		k=mark(way,mark_way,mz,step,ex_point);
		step++;
	}
	if(ex_point[0][0]=='\0'){
		return 1;	
	}
	else{
		exp_x=ex_point[0][0];
		exp_y=ex_point[0][1];
		calculate_exit(mz,exp_x,exp_y);
		return 0;
	}
}

int mark(int way[MAX][2],int mark_way[MAX][2],int mz[ARRAY][ARRAY],int step,int ex_p[MAX][2]){
	int i=0,j=0,x,y;
	while(way[i][0]!='\0'){
		x=way[i][0];
		y=way[i][1];
		if(east(mz,x,y)==0){
			mz[x][y+1]=step+1;
			mark_way[j][0]=x;
			mark_way[j][1]=y+1;
			if(check_exit(x,y+1)){
				ex_p[0][0]=x;
				ex_p[0][1]=y+1;
				ex_p[1][0]='\0';
				mark_way[0][0]='\0';
				return 0;
			}
			j++;
		}
		if(sorth(mz,x,y)==0){
			mz[x+1][y]=step+1;
			mark_way[j][0]=x+1;
			mark_way[j][1]=y;
			if(check_exit(x+1,y)){
				ex_p[0][0]=x+1;
				ex_p[0][1]=y;
				ex_p[1][0]='\0';
				mark_way[0][0]='\0';
				return 0;
			}
			j++;
		}
		if(west(mz,x,y)==0){
			mz[x][y-1]=step+1;
			mark_way[j][0]=x;
			mark_way[j][1]=y-1;
			if(check_exit(x,y-1)){
				ex_p[0][0]=x;
				ex_p[0][1]=y-1;
				ex_p[1][0]='\0';
				mark_way[0][0]='\0';
				return 0;
			}
			j++;
		}
		if(north(mz,x,y)==0){
			mz[x-1][y]=step+1;
			mark_way[j][0]=x-1;
			mark_way[j][1]=y;
			if(check_exit(x-1,y)){
				ex_p[0][0]=x-1;
				ex_p[0][1]=y;
				ex_p[1][0]='\0';
				mark_way[0][0]='\0';
				return 0;
			}
			j++;
		}
		i++;
	}

	mark_way[j][0]='\0';
	if(j!=0){
		copy(way,mark_way);
	}
	else{
		ex_p[0][0]='\0';
	}
	return j;
}

int check_exit(int x,int y){
	if(x==0||y==0||x==LENGH ||y==LENGH )
		return 1;
	else
		return 0;
}

int copy(int way[MAX][2],int mark_way[MAX][2]){
	int i=0,x,y;
	while(mark_way[i][0]!='\0'){
		way[i][0]=mark_way[i][0];
		way[i][1]=mark_way[i][1];
		x=mark_way[i][0];
		y=mark_way[i][1];
		i++;
	}
	way[i][0]='\0';
	return 0;
}

int east(int mz[ARRAY ][ARRAY ],int x, int y){
	return mz[x][y+1];
}
int sorth(int mz[ARRAY ][ARRAY ],int x, int y){
	return mz[x+1][y];
}
int west(int mz[ARRAY ][ARRAY ],int x, int y){
	return mz[x][y-1];
}
int north(int mz[ARRAY ][ARRAY ],int x, int y){
	return mz[x-1][y];
}

int display(int mz[ARRAY ][ARRAY ]){
	int i,j;
	for (i=0;i<10;i++){
		for(j=0;j<10;j++){
			if(mz[i][j]==9999){
				printf("#");
			}
			else if(mz[i][j]==1){
				printf(".");
			}
			else{
				printf(" ");
			}
		}
	printf("\n");
	}
	return 0;
}

int calculate_exit(int mz[ARRAY][ARRAY],int x, int y){
	int i=x,j=y,temp=mz[i][j];
		while(mz[i][j]!=1){
		if(east(mz,i,j)==temp-1){
			mz[i][j]=1;
			j++;			
		}
		if(sorth(mz,i,j)==temp-1){
			mz[i][j]=1;
			i++;			
		}
		if(west(mz,i,j)==temp-1){
			mz[i][j]=1;
			j--;			
		}
		if(north(mz,i,j)==temp-1){
			mz[i][j]=1;
			i--;			
		}
		temp--;
	}
	return 0;
}