P1238 走迷宫

admin

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)

张笑宇

忘记把起点变成走过了......
导致多交了一次

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. */

复制代码

黄煦喆

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

#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;
}

李思矿

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

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

///这题老阴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;
}