深夜的水管工 经典算法

红绯鱼

#include<iostream>   
//《啊哈算法》P117
//写代码的时候一定要非常小心，一个错字符就可能浪费掉你几个小时
using namespace std;

int n,m,flag;
int a[51][51],b[51][51];



struct node  //这种情况下比STL好用
{
        int x;
        int y;
}s[100];
int top=0;

void dfs(int x,int y,int front)
{
        int i;
        if(x==n&&y==m+1)//中间如果加逗号是或的意思
        {
                flag=1;
                for(i=1;i<=top;i++) //放在这里是应为放底下会被全部弹出
                cout<<"("<<s[i].x<<","<<s[i].y<<")-->";
                cout<<top<<"步"<<endl;
                return;
        }
        if(x<1||x>n||y<1||y>m)return;
        if(b[x][y]==1)return;
        b[x][y]=1;
       
        top++;
        s[top].x=x;
        s[top].y=y;
       
        if(a[x][y]==1)//x对应行，y对应列，，，不要搞反了
        {
               
                if(front==1)dfs(x,y+1,1);
                if(front==2)dfs(x+1,y,2);
                if(front==3)dfs(x,y-1,3);
                if(front==4)dfs(x-1,y,4);
        }
       
        if(a[x][y]==2)
        {
                if(front==1)dfs(x-1,y,4),dfs(x+1,y,2);//逗号的应用
                if(front==2)dfs(x,y-1,3),dfs(x,y+1,1);
                if(front==3)dfs(x-1,y,4),dfs(x+1,y,2);
                if(front==4)dfs(x,y-1,3),dfs(x,y+1,1);
       
        }
       
        b[x][y]=0;
        top--;  //要记得弹出不然路径里就会多好多东西
        return;
}

int main()
{
        int i,j;
        cin>>n>>m;
        for(i=1;i<=n;i++)for(j=1;j<=m;j++)cin>>a[i][j];
        dfs(1,1,1);
        if(flag)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
       
       
        cin>>i;
        return 0;
}

红绯鱼

睡觉喽aaaaaaaaaaaaaaaa