华师一附中OI组

标题: P1238 走迷宫 [打印本页]
作者: admin    时间: 2018-5-12 22:38
标题: P1238 走迷宫
https://www.luogu.org/problemnew/show/P1238
题目描述
有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。

优先顺序：左上右下

输入输出格式
输入格式：
第一行是两个数m，n(1<m，n<15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。

输出格式：
所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“一>”表示方向。

如果没有一条可行的路则输出-1。

输入输出样例
输入样例#1：
5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6
输出样例#1：
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
作者: 张笑宇    时间: 2018-5-24 22:52
忘记把起点变成走过了......
导致多交了一次


  1. #include<iostream>
  2. using namespace std;
  3. int x,y,i,j;
  4. const int mx=20,mn=400;
  5. int a[mx][mx],wayx[mn],wayy[mn];///way x/y 记录路径
  6. bool b[mx][mx];///b记录是否走过
  7. int ax,ay,bx,by;///ax,ay起点 bx,by终点
  8. int dx[5]= {0,0,-1,0,1};
  9. int dy[5]= {0,-1,0,1,0}; ///左上右下
  10. bool bb=0;///有没有解
  11. void dfs(int s,int px,int py)///s第几步
  12. {
  13.     if (px==bx && py==by)///若到达终点
  14.     {
  15.         bb=1;
  16.         for (i=1; i<=s-1; i++)
  17.         {
  18.             cout<<"("<<wayx[i]<<","<<wayy[i]<<")->";
  19.         }
  20.         cout<<"("<<bx<<","<<by<<")"<<endl;
  21.     }
  22.     else
  23.     {
  24.         int k;
  25.         for (k=1; k<=4; k++)
  26.         {
  27.             int tx=px+dx[k];
  28.             int ty=py+dy[k];
  29.             if (1<=tx&&tx<=x&&1<=ty&&ty<=y&&a[tx][ty]==1&&b[tx][ty]==0)
  30.             {
  31.                 ///cout<<px<<" "<<py<<endl;
  32.                 wayx[s]=px;
  33.                 wayy[s]=py;
  34.                 b[tx][ty]=1;
  35.                 dfs(s+1,tx,ty);
  36.                 b[tx][ty]=0;
  37.             }
  38.         }
  39.     }
  40. }
  41. int main()
  42. {
  43.     cin>>x>>y;
  44.     for (i=1; i<=x; i++)
  45.         for (j=1; j<=y; j++) cin>>a[i][j],b[i][j]=0;
  46.     cin>>ax>>ay>>bx>>by;
  47.     b[ax][ay]=1;
  48.     dfs(1,ax,ay);
  49.     if (bb==0) cout<<"-1";
  50.     return 0;
  51. }
  52. /*
  53. 5 6
  54. 1 0 0 1 0 1
  55. 1 1 1 1 1 1
  56. 0 0 1 1 1 0
  57. 1 1 1 1 1 0
  58. 1 1 1 0 1 1
  59. 1 1
  60. 5 6
  61. */
复制代码
作者: 黄煦喆    时间: 2018-5-26 19:10
本帖最后由 黄煦喆 于 2018-5-26 19:11 编辑
  1. #include<iostream>
  2. using namespace std;
  3. int m,n,x0,y0,x1,y1,num=1;
  4. int a[20][20],b[20][20],t;
  5. int mx[300],my[300],tx,ty;
  6. int ax[5]={0,+0,-1,+0,+1};
  7. int ay[5]={0,-1,+0,+1,+0};
  8. void print()
  9. {
  10.     for(int i=1;i<num;i++)
  11.         cout<<'('<<mx[i]<<','<<my[i]<<')'<<"->";
  12.     cout<<'('<<x1<<','<<y1<<')'<<endl;
  13.     t++;
  14. }
  15. void ms(int x,int y)
  16. {
  17.     if(x==x1&&y==y1)print();
  18.     else for(int i=1;i<=4;i++)
  19.     {
  20.         tx=x+ax[i];
  21.         ty=y+ay[i];
  22.         if(a[tx][ty]==1&&b[tx][ty]==0)
  23.         {
  24.             b[x][y]=1;
  25.             mx[num]=x;
  26.             my[num]=y;
  27.             num++;
  28.             ms(tx,ty);
  29.             b[x][y]=0;
  30.             num--;
  31.         }
  32.     }
  33. }
  34. int main()
  35. {
  36.     cin>>m>>n;
  37.     for(int i=1;i<=m;i++)
  38.         for(int j=1;j<=n;j++)
  39.         cin>>a[i][j];
  40.     cin>>x0>>y0;
  41.     cin>>x1>>y1;
  42.     ms(x0,y0);
  43.     if(!t)cout<<-1;
  44.     return 0;
  45. }
复制代码
作者: YTC    时间: 2018-5-28 11:05
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int dx[]={+0,-1,+0,+1};
const int dy[]={-1,+0,+1,+0};
const int base=16;
int m,n,stx,sty,enx,eny;
int a[16][16];
bool v[16][16];
int step[501];
bool p;
void dfs(int x,int y,int dep)
{
    //cout<<x<<' '<<y<<endl;
    if(x==enx&&y==eny)
    {
        p=1;
        for(int i=1;i<dep;i++) cout<<"("<<step[i]/base<<','<<step[i]%base<<")->";
        cout<<"("<<step[dep]/base<<','<<step[dep]%base<<")"<<endl;
    }
    for(int i=0;i<=3;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<=0||xx>m||yy<=0||yy>n) continue;
        if(a[xx][yy]&&!v[xx][yy])
        {
            v[xx][yy]=1;
            step[dep+1]=xx*base+yy;
            dfs(xx,yy,dep+1);
            v[xx][yy]=0;
        }
    }
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        cin>>a[i][j];
    cin>>stx>>sty;
    cin>>enx>>eny;
    step[1]=stx*base+sty;
    v[stx][sty]=1;
    dfs(stx,sty,1);
    if(!p) cout<<-1;
    return 0;
}
作者: 李思矿    时间: 2018-6-4 13:52
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. #define MAXN 20
  5. int m,n,G[MAXN][MAXN],sx,sy,tx,ty;
  6. int hjj[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
  7. bool ok;
  8. string trans(int be)
  9. {
  10.     string tmp="";
  11.     int tmpint=be;
  12.     while(tmpint)
  13.     {
  14.         tmp+=tmpint%10+'0';
  15.         tmpint/=10;
  16.     }
  17.     reverse(tmp.begin(),tmp.end());
  18.     return tmp;
  19. }
  20. void dfs(int x,int y,string now)
  21. {
  22.     if(x==tx&&y==ty)
  23.     {
  24.         ok=true;
  25.         cout<<now<<endl;
  26.         return ;
  27.     }
  28.     for(int i=0;i<4;i++)
  29.     {
  30.         if(G[x+hjj[i][0]][y+hjj[i][1]])
  31.         {
  32.             G[x+hjj[i][0]][y+hjj[i][1]]=0;
  33.             string str=now;
  34.             str+="->(";
  35.             str+=trans(x+hjj[i][0]);
  36.             str+=',';
  37.             str+=trans(y+hjj[i][1]);
  38.             str+=')';
  39.             dfs(x+hjj[i][0],y+hjj[i][1],str);
  40.             G[x+hjj[i][0]][y+hjj[i][1]]=1;
  41.         }
  42.     }
  43. }
  44. int main()
  45. {
  46.     cin>>m>>n;
  47.     for(int i=1;i<=m;i++)
  48.         for(int j=1;j<=n;j++)
  49.             cin>>G[i][j];
  50.     cin>>sx>>sy>>tx>>ty;
  51.     if(!G[sx][sy])
  52.     {
  53.         cout<<-1;
  54.         return 0;
  55.     }
  56.     G[sx][sy]=0;
  57.     string str="";
  58.     str+='(';
  59.     str+=trans(sx);
  60.     str+=',';
  61.     str+=trans(sy);
  62.     str+=')';
  63.     dfs(sx,sy,str);
  64.     if(!ok) cout<<-1;
  65.     return 0;
  66. }
复制代码
作者: Scorpio    时间: 2018-7-2 22:09
  1. #include<iostream>
  2. using namespace std;
  3. int a[16][16],wx[226],wy[226],b[16][16],dx[5]{0,0,-1,0,1},dy[5]{0,-1,0,1,0};
  4. int m,n,i,j,xx,yy,xxx,yyy,l,bb;
  5. void hhh(int x,int y,int k)
  6. {
  7.     int i,j;
  8.     if(x==xxx&&y==yyy)
  9.     {
  10.         bb=1;
  11.         for(i=1;i<=k-1;i++)
  12.         {
  13.             if(i==1)
  14.                 cout<<"("<<wx[i]<<","<<wy[i]<<")";
  15.             else
  16.                 cout<<"->("<<wx[i]<<","<<wy[i]<<")";
  17.         }
  18.         cout<<endl;
  19.     }
  20.     else for(j=1;j<=4;j++)
  21.     {
  22.         if(b[x+dx[j]][y+dy[j]]==0&&a[x+dx[j]][y+dy[j]]==1&&x+dx[j]>=1&&x+dx[j]<=m&&y+dy[j]>=1&&y+dy[j]<=n)
  23.         {
  24.             wx[k]=x+dx[j];
  25.             wy[k]=y+dy[j];
  26.             b[x+dx[j]][y+dy[j]]=1;
  27.             hhh(x+dx[j],y+dy[j],k+1);
  28.             b[x+dx[j]][y+dy[j]]=0;
  29.         }
  30.     }
  31. }
  32. int main()
  33. {
  34.     cin>>m>>n;
  35.     for(i=1;i<=m;i++)
  36.         for(j=1;j<=n;j++)
  37.             cin>>a[i][j];
  38.     cin>>xx>>yy>>xxx>>yyy;
  39.     b[xx][yy]=1;
  40.     wx[1]=1;
  41.     wy[1]=1;
  42.     l=1;
  43.     hhh(xx,yy,2);
  44.     if(bb==0)
  45.         cout<<-1;
  46.     return 0;
  47. }
复制代码
作者: t20020125    时间: 2018-10-4 18:30
///这题老阴p，还有个搜索的顺序
#include<bits/stdc++.h>
using namespace std;
const int mm=300;
int xx1,yy1;
int xx2,yy2;
int lur[mm];
int luc[mm];
bool b[20][20];
int a[20][20];
int flag;
void dfs(int r,int c,int tp)
{
    b[r][c]=1;
    lur[tp]=r;
    luc[tp]=c;
    if(r==xx2&&c==yy2)
    {
        flag=1;
        for(int i=1; i<=tp; i++)
        {
            cout<<'('<<lur[i]<<','<<luc[i]<<')';
            if(i!=tp)cout<<"->";

        }
        cout<<endl;
        b[r][c]=0;
        return;
    }

    if(a[r][c-1]!=0&&b[r][c-1]==0)
        dfs(r,c-1,tp+1);
    if(a[r-1][c]!=0&&b[r-1][c]==0)
        dfs(r-1,c,tp+1);
    if(a[r][c+1]!=0&&b[r][c+1]==0)
        dfs(r,c+1,tp+1);
    if(a[r+1][c]!=0&&b[r+1][c]==0)
        dfs(r+1,c,tp+1);
    b[r][c]=0;
}
int main()
{
    memset(b,-1,sizeof(b));
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            cin>>a[i][j];
            b[i][j]=0;
        }

    cin>>xx1>>yy1;
    cin>>xx2>>yy2;
    dfs(xx1,yy1,1);
    if(flag==0)cout<<-1;
    return 0;
}




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2