简单水池&&迷宫问题

时间：2023-12-20 21:27:38
#include <iostream>

#include <stdio.h>

#include <cstring>

using namespace std;

int M[101][101],flag[101][101];

int n,m;

int cnt;

void pool(int x,int y)

{

    flag[x][y]=1;

    M[x][y]=cnt;

    if(x-1>=1&&M[x-1][y]!=0&&flag[x-1][y]==0)  pool(x-1,y);

    if(x+1<=n&&M[x+1][y]!=0&&flag[x+1][y]==0)  pool(x+1,y);

    if(y-1>=1&&M[x][y-1]!=0&&flag[x][y-1]==0)  pool(x,y-1);

    if(y+1<=m&&M[x][y+1]!=0&&flag[x][y+1]==0)  pool(x,y+1);

}

int main()

{

    int i,j,t;

    cin>>t;

    while(cin>>n>>m&&t--)

    {

        cnt=0;

    for(i=1;i<=n;i++)

        for(j=1;j<=m;j++)

            cin>>M[i][j];

            //cout<<endl;

           // memset(m,0,sizeof(m));

            memset(flag,0,sizeof(flag));

    for(i=1;i<=n;i++)

        for(j=1;j<=m;j++)

        if(M[i][j]==1&&flag[i][j]==0)

        {

            cnt++;pool(i,j);

        }

        printf("%d\n",cnt);

         // for(i=1;i<=n;cout<<endl,i++)

         //       for(j=1;j<=m;j++)

         //       cout<<M[i][j]<<" ";

    }

    return 0;

    }

//这一道题是有关搜索的，看看就行
#include <iostream>

#include <cstring>

using namespace std;

int a,b,c,d,sum,cnt;

int M[9][9]={

 {1,1,1,1,1,1,1,1,1},

 {1,0,0,1,0,0,1,0,1},

 {1,0,0,1,1,0,0,0,1},

 {1,0,1,0,1,1,0,1,1},

 {1,0,0,0,0,1,0,0,1},

 {1,1,0,1,0,1,0,0,1},

 {1,1,0,1,0,1,0,0,1},

 {1,1,0,1,0,0,0,0,1},

 {1,1,1,1,1,1,1,1,1}};

void dfs(int x,int y,int cnt)

{

    if(x==c&&y==d)  {if(cnt<sum) sum=cnt;}

    else{

    if(!M[x-1][y])  {M[x-1][y]=1; dfs(x-1,y,cnt+1); M[x-1][y]=0;}

    if(!M[x+1][y])  {M[x+1][y]=1; dfs(x+1,y,cnt+1); M[x+1][y]=0;}

    if(!M[x][y-1])  {M[x][y-1]=1; dfs(x,y-1,cnt+1); M[x][y-1]=0;}

    if(!M[x][y+1])  {M[x][y+1]=1; dfs(x,y+1,cnt+1); M[x][y+1]=0;}

    }

}

int main()

{

    int t;

    cin>>t;

    while(t--&&cin>>a>>b>>c>>d)

    {

        cnt=0,sum=81;

        dfs(a,b,cnt);

        cout<<sum<<endl;

    }

    return 0;

}

这道题的代码，一开始不是这样写的，我另外定义一个flag，把每次访问的都标记，不过后面觉得这个是多此一举，可以在原来的数组上面，每次访问过后，都标记为墙1，这样就ok了，还有一个就是求最小的值，这个在dfs函数里面开始就给一个判断，其实大概的思路就是先找到一条路，记下步数，然后每次回溯，还原被标记的点，这样继续求出其他路径的值。。。。

#include <iostream>

#include <cstring>

using namespace std;

int M[9][9]={

 {1,1,1,1,1,1,1,1,1},

 {1,0,0,1,0,0,1,0,1},

 {1,0,0,1,1,0,0,0,1},

 {1,0,1,0,1,1,0,1,1},

 {1,0,0,0,0,1,0,0,1},

 {1,1,0,1,0,1,0,0,1},

 {1,1,0,1,0,1,0,0,1},

 {1,1,0,1,0,0,0,0,1},

 {1,1,1,1,1,1,1,1,1}},flag[100][100];

int n,m,cnt=0;

int a,b,c,d;

void maze(int x,int y)

{

    if(x==c&&y==d)  return;

    flag[x][y]=1;

    if(x-1>=0&&M[x-1][y]==0&&flag[x-1][y]==0)  {cnt++;  maze(x-1,y);  cnt--;flag[x-1][y]=0;}

    if(x+1<=8&&M[x+1][y]==0&&flag[x+1][y]==0)  {cnt++;  maze(x+1,y);  cnt--;flag[x+1][y]=0;}

    if(y-1>=0&&M[x][y-1]==0&&flag[x][y-1]==0)  {cnt++;  maze(x,y-1);  cnt--;flag[x][y-1]=0;}

    if(y+1<=8&&M[x][y+1]==0&&flag[x][y+1]==0)  {cnt++;  maze(x,y+1);  cnt--;flag[x][y+1]=0;}

}

int main()

{

    //int i,j;

    cin>>a>>b>>c>>d;

    memset(flag,0,sizeof(flag));

    //for(i=a;i<=8;i++)

     //   for(j=b;j<=8;j++)

            maze(a,b);

            cout<<cnt<<endl;

    return 0;

}

后面想把路径打印出来，可是出不来，代码如下

#include <iostream>

#include <cstring>

using namespace std;

int a,b,c,d,sum,cnt,LJ1[1000],LJ2[1000],h,k;

int M[9][9]={

 {1,1,1,1,1,1,1,1,1},

 {1,0,0,1,0,0,1,0,1},

 {1,0,0,1,1,0,0,0,1},

 {1,0,1,0,1,1,0,1,1},

 {1,0,0,0,0,1,0,0,1},

 {1,1,0,1,0,1,0,0,1},

 {1,1,0,1,0,1,0,0,1},

 {1,1,0,1,0,0,0,0,1},

 {1,1,1,1,1,1,1,1,1}};

void dfs(int x,int y,int cnt)

{

    LJ1[k++]=x;LJ2[h++]=y;

    if(x==c&&y==d)  {if(cnt<sum) sum=cnt;}

    else{

    if(!M[x-1][y])  {M[x-1][y]=1; dfs(x-1,y,cnt+1); M[x-1][y]=0;LJ1[k-1]=0;LJ2[h-1]=0;}

    if(!M[x+1][y])  {M[x+1][y]=1; dfs(x+1,y,cnt+1); M[x+1][y]=0;LJ1[k-1]=0;LJ2[h-1]=0;}

    if(!M[x][y-1])  {M[x][y-1]=1; dfs(x,y-1,cnt+1); M[x][y-1]=0;LJ1[k-1]=0;LJ2[h-1]=0;}

    if(!M[x][y+1])  {M[x][y+1]=1; dfs(x,y+1,cnt+1); M[x][y+1]=0;LJ1[k-1]=0;LJ2[h-1]=0;}

    }

}

int main()

{

    int t,i;

    cin>>t;

    while(t--&&cin>>a>>b>>c>>d)

    {

        k=0;h=0;

        memset(LJ1,0,sizeof(LJ1));

        memset(LJ2,0,sizeof(LJ2));

        cnt=0,sum=81;

        dfs(a,b,cnt);

        cout<<sum<<endl;

        for(i=0;i<=100;i++)

            cout<<LJ1[i]<<","<<LJ2[i]<<" → ";

    }

    return 0;

}

//怎么把路径打印出来，感觉如果走一条路不通，就标记为0，可是又有回溯，就感觉全乱了，如果在每次dfs后，干脆数组全为0，k，h也从0开始应该可以。。。

#include <iostream>

#include <mem.h>

using namespace std;

char M[30][30];

bool Find;

int flag[30][30];

int n,m;

void ss(int x,int y)

{

    if(Find==true)  return ;

    cout<<x<<" "<<y<<" →";

    flag[x][y]=1;

    int a,b;

    int i;

    //上走

    a=x-1;

    b=y;

    if(a>=1&&M[a][b]!='w'&&flag[a][b]==0)

    {

        if(M[a][b]=='T')

        {

            Find=true;

            return ;

        }

        ss(a,b);

    }

    //下走

     a=x+1;

     b=y;

//cout<<a<<n<<endl;

    if(a<=n&&M[a][b]!='w'&&flag[a][b]==0)

    {

        if(M[a][b]=='T')

        {

            Find=true;

            return ;

        }

        ss(a,b);

    }

    //左走

     a=x;

    b=y-1;

    if(b>0&&M[a][b]!='w'&&flag[a][b]==0)

    {

        if(M[a][b]=='T')

        {

            Find=true;

            return ;

        }

        ss(a,b);

    }

    //右走

     a=x;

    b=y+1;

    if(b<=m&&M[a][b]!='w'&&flag[a][b]==0)

    {

        if(M[a][b]=='T')

        {

            Find=true;

            return ;

        }

        ss(a,b);

    }

}

int main()

{

    int j,i,x,y;

    cin>>n>>m;

    for(i=1;i<=n;i++)

        for(j=1;j<=m;j++)

    {

        cin>>M[i][j];

        if(M[i][j]=='s')  {x=i;y=j;}

    }

    memset(flag,0,sizeof(flag));

    ss(x,y);

    return 0;

}

//一个迷宫的问题，和水池问题是一个题型，不多讲了。。。。

相关文章