POJ P3009 Curling 2.0 题解

小鱼儿 2021-10-29 13:16 214阅读 0赞

深搜，向四个方向，在不越界的情况下一直闷头走，直到撞墙。到达终点就输出，没到就回溯。

1 #include<iostream>
     2 #include<cstring>
     3 #include<cstdio>
     4 #include<algorithm>
     5 using namespace std;
     6 int n,m;
     7 int map[21][21];
     8 int xxx,yyy;
     9 int ans=99999999;
    10 int tx[4]={
        1,-1,0,0};
    11 int ty[4]={
        0,0,1,-1};
    12 void dfs(int x,int y,int step)
    13 {
    14     if(step>=ans||step>=10)
    15     {
    16         return;
    17     }
    18     for(int i=0;i<4;i++)
    19     {
    20         int sx=x+tx[i];
    21         int sy=y+ty[i];
    22         if(map[sx][sy]==1)continue;
    23         while(sx>=0&&sy>=0&&sx<n&&sy<m&&map[sx][sy]!=1&&map[sx][sy]!=3)
    24         {
    25             sx+=tx[i];
    26             sy+=ty[i];
    27         }
    28         if(sx<0||sy<0||sx==n||sy==m)continue;
    29         else 
    30         {
    31             if(map[sx][sy]==3)
    32             {
    33                 ans=step+1;
    34                 return;
    35             }
    36             else 
    37             {
    38                 map[sx][sy]=0;
    39                 dfs(sx-tx[i],sy-ty[i],step+1);
    40                 map[sx][sy]=1;
    41             }
    42         }
    43     }
    44 }
    45 int main()
    46 {
    47     while(cin>>m>>n&&n!=0&&m!=0)
    48     {
    49         ans=99999999;
    50         for(int i=0;i<n;i++)
    51         {
    52             for(int j=0;j<m;j++)
    53             {
    54                 cin>>map[i][j];
    55                 if(map[i][j]==2)
    56                 {
    57                     xxx=i;
    58                     yyy=j;
    59                 }
    60             }
    61         }
    62         dfs(xxx,yyy,0);
    63         if(ans==99999999) cout<<-1<<endl;
    64         else cout<<ans<<endl;
    65     }
    66 }
    请各位大佬斧正（反正我不认识斧正是什么意思）

转载于:https://www.cnblogs.com/handsome-zyc/p/11237412.html