走迷宫

分手后的思念是犯贱 2022-07-13 13:40 230阅读 0赞

Problem Description

有一个m\*n格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，输入这m\*n个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用-1表示无路）。

Input

第一行是两个数m，n（1< m, n< 15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。

Output

所有可行的路径，输出时按照左上右下的顺序。描述一个点时用（x，y）的形式，除开始点外，其他的都要用“->”表示。如果没有一条可行的路则输出-1。

Example Input

5 4
    1 1 0 0
    1 1 1 1
    0 1 1 0
    1 1 0 1
    1 1 1 1
    1 1
    5 4

Example Output

(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
    (1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
    (1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
    (1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
    (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
    (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
    (1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
    (1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4

#include<stdio.h>
    int n,m;
    int a[16][16];
    int book[16][16];
    int flag=0;
    void dfs (int x,int y,int mx,int my,int line[230][2],int u) {
    	int i,tx,ty;
    	int k=u;
    	int next[4][2]= { {
    			0,-1
    		}
    		, {
    			-1,0
    		}
    		, {
    			0,1
    		}
    		, {
    			1,0
    		}
    	}
    	;
    	if(x==mx&&y==my) {
    		for (i=0;i<u;i++) {
    			if(i!=u-1) {
    				printf("(%d,%d)->",line[i][0],line[i][1]);
    			} else
    			                printf("(%d,%d)\n",line[i][0],line[i][1]);
    		}
    		flag=1;
    	}
    	for (i=0;i<4;i++) {
    		tx=x+next[i][0];
    		ty=y+next[i][1];
    		if(tx<1||tx>n||ty<1||ty>m)
    		            continue;
    		if(book[tx][ty]==0 && a[tx][ty]==1) {
    			line[u][0]=tx;
    			line[u][1]=ty;
    			k=u+1;
    			book[tx][ty]=1;
    			dfs(tx,ty,mx,my,line,k);
    			book[tx][ty]=0;
    		}
    	}
    	return ;
    }
    int main() {
    	int i,j;
    	int x,y,mx,my;
    	int u=0;
    	int line[230][2]= {
    		0
    	}
    	;
    	scanf("%d%d",&n,&m);
    	for (i=1;i<=n;i++) {
    		for (j=1;j<=m;j++) {
    			scanf("%d",&a[i][j]);
    		}
    	}
    	scanf("%d%d%d%d",&x,&y,&mx,&my);
    	book[x][y]=1;
    	line[u][0]=x;
    	line[u][1]=y;
    	u++;
    	dfs(x,y,mx,my,line,u);
    	if(flag==0)
    	        printf("-1\n");
    	return 0;
    }