走迷宫

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> #include<string.h> int m , n , step, x1,y1,x2,y2,flag; int map[16][16]; int visit[16][16]; int next[4][2] = {{-1,0},{0,-1},{0,1},{1,0}}; struct node {     int x,y; }path[100]; void dfs(int x,int y) {     int i ,k1,k2;     if(x==x2&&y==y2)     {         flag = 1;         for(i = 0;i<step-1;i++)         {             printf("(%d,%d)->",path[i].x,path[i].y);         }             printf("(%d,%d)\n",x2,y2);             return ;     }         for(i = 0;i<4;i++)         {             k1 = x+next[i][0];             k2 = y+next[i][1];             if(k1>=1&&k1<=m&&k2&&n&&!visit[k1][k2]&&map[k1][k2])             {                 path[step].x = k1;                 path[step++].y = k2;                 visit[k1][k2] = 1;                 dfs(k1,k2);                 visit[k1][k2] = 0;                 step--;              }         } } int main() {     int i,j;     while(~scanf("%d %d",&m,&n))     {         flag = 0;         memset(path,-1,sizeof(path));         memset(visit,0,sizeof(visit));         for(i = 1;i<=m;i++ )         {             for(j = 1;j<=n;j++)             {                 scanf("%d",&map[i][j]);             }         }         scanf("%d%d",&x1,&y1);         scanf("%d%d",&x2,&y2);         visit[x1][y1] = 1;         step = 0;         path[step].x = x1;         path[step++].y = y1;         dfs(x1,y1);         if(!flag)             printf("-1\n");     }     return 0; }