当前位置: 代码迷 >> 综合 >> 走迷宫 oj
  详细解决方案

走迷宫 oj

热度:70   发布时间:2024-01-14 22:36:06.0

走迷宫

Time Limit: 1000 ms  Memory Limit: 65536 KiB
Submit  Statistic
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。
Sample 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
Sample 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)
Hint
Source
#include<stdio.h>  
#include<string.h>  
#include<vector>  
#include<queue>  
using namespace std;  
const int maxn =30;  
const int dx[] = {0,-1,0,1};  
const int dy[] = {-1,0,1,0};  
int a[maxn][maxn];  
int vis[maxn][maxn];  
int aa[maxn*maxn][3];  
int n,m,e_x,e_y;  
bool f = false;  
inline bool inside(int x,int y)  
{  return x>=1&&x<=n&&y>=1&&y<=m&&a[x][y];  
}  
void dfs(int x,int y,int d)  
{  if(x==e_x &&y ==e_y)  {  for(int i=0;i<d-1;i++)  {  printf("(%d,%d)->",aa[i][0],aa[i][1]);  }  printf("(%d,%d)\n",e_x,e_y);  f = true;  return ;  }  for(int i=0;i<4;i++)  {  int xx=x+dx[i];  int yy =y +dy[i];  if(inside(xx,yy)&&!vis[xx][yy])  {  vis[xx][yy] = 1;  aa[d][0] = xx;  aa[d][1] = yy;  dfs(xx,yy,d+1);  vis[xx][yy]  = 0;  }  }  }  
int main()  
{  scanf("%d%d",&n,&m);  for(int i=1;i<=n;i++)  for(int j=1;j<=m;j++)  scanf("%d",&a[i][j]);  int f_x,f_y;  scanf("%d%d%d%d",&f_x,&f_y,&e_x,&e_y);  if(f_x==e_x&&f_y==e_y)  {  printf("-1\n");  return 0;  }  aa[0][0] = f_x;  aa[0][1] = f_y;  vis[f_x][f_y] = 1;  dfs(f_x,f_y,1);  if(!f)printf("-1");  return 0;  } 

  相关解决方案