首页 > 代码库 > HDU 1010 Tempter of the Bone(DFS)

HDU 1010 Tempter of the Bone(DFS)

2024-08-14 13:54:09   210人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1010

题目大意：

　　输入 n m t,生成 n*m 矩阵,矩阵元素由 ‘.’ ‘S‘ ‘D‘ ‘X‘ 四类元素组成.

　　S‘代表是开始位置； ‘D‘表示结束位置；‘.‘表示可以走的路；‘X‘表示是墙。

　　问:从‘S’  能否在第 t 步 正好走到 ‘D‘. 

解题思路：

　　

 1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,t; 4 int doorX,doorY; 5 char ca[10][10]; 6 int to[4][2] = {{0,-1},{0,1},{-1,0},{1,0}}; 7 int dfs(int x,int y,int cnt) 8 { 9     if(x>n||y>m||x<=0||y<=0)return 0;10     if(cnt==t&&x==doorX&&y==doorY)11         return 1;12     int tem=t-cnt-abs(x-doorX)-abs(y-doorY);13     if(tem<0 || tem&1 )return 0;14     for(int i=0; i<4; i++)15     {16         if(ca[x+to[i][0]][y+to[i][1]]!=‘X‘)17         {18             ca[x+to[i][0]][y+to[i][1]]=‘X‘;19             if(dfs(x+to[i][0],y+to[i][1],cnt+1))return 1;20             ca[x+to[i][0]][y+to[i][1]]=‘.‘;21         }22     }23     return 0;24 }25 int main()26 {27     while(scanf("%d%d%d",&n,&m,&t)!=EOF&&n+m+t)28     {29         int i,j,wall=0,stratX,stratY;30         getchar();31         for(i=1; i<=n; i++)32         {33             for(j=1; j<=m; j++)34             {35                 scanf("%c",&ca[i][j]);36                 if(ca[i][j]==‘S‘)37                     stratX=i,stratY=j;38                 else if(ca[i][j]==‘X‘)39                     wall++;40                 else if(ca[i][j]==‘D‘)41                     doorX=i,doorY=j;42             }43             getchar();44         }45         if(n*m-wall<=t)46         {47             printf("NO\n");48             continue;49         }50         ca[stratX][stratY]=‘X‘;51         if(dfs(stratX,stratY,0))52             printf("YES\n");53         else54             printf("NO\n");55     }56     return 0;57 }

 

HDU 1010 Tempter of the Bone(DFS)


联系
我们