DesertWind TopCoder - 1570 DP+搜索 hqg_ac

$DesertWind$ $TopCoder$ $-$ $1570$

题意：有一张地图,”_”表示沙漠,”@”表示起点,”X”表示障碍物,”*”表示终点（终点可能有多个）

当你准备往一个格子进发时，你会知道当天的风向。如果你逆风走要3天，不逆风1天。

现在问你在最坏情况下最少要走多少天

$Tc$的题的题面都很绕，$min max$ 层层套。。。

题解：

这个题目还是比较水的，关键在题意理解

你肯定尽可能最短路，控制风向的人肯定是让你的最短路径可能的长，好似一场博弈

这又是一道$DP$与图论(搜索)结合的题

$dp[i][j]$表示到达$i,j$的最坏天数

$dp[i][j]$肯定从八个方向$(tx,ty)$推得。

对于$dp[tx][ty]$中最小的，控制风向的人必定使得风向与之相反，而你肯定会走第二小的

于是 dp[i][j]=min(dp[i][j],max(dp[tx1][ty1]+3，dp[tx2][ty2]+1) d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , m a x ( d p [ t x 1 ] [ t y 1 ] + 3 ， d p [ t x 2 ] [ t y 2 ] + 1 ) $dp[i][j]=min(dp[i][j],max(dp[tx1][ty1]+3，dp[tx2][ty2]+1)$

$dp[tx1][ty1]$是最小的，$dp[tx2][ty2]$是第二小的

最后答案就是$dp[s][t]$

#include 
using namespace std ;
const int N=100 ;
int dx[8]={-1,-1,-1,0,0,1,1,1} ;
int dy[8]={-1,0,1,-1,1,-1,0,1} ;
class DesertWind{
public:int n,m,s,t; int dp[N][N],a[N][N],tmp[10] ;bool check(int x,int y){return (x>0 && y>0 && x<=n && y<=m) ;}int change(char c){if (c=='-') return 1 ;if (c=='X') return 2 ;if (c=='@') return 3 ;if (c=='*') return 4 ; }int daysNeeded(vector <string> theMap){memset(dp,0x3f,sizeof(dp)); n=theMap.size();m=theMap[1].size() ;for (int i=0;ifor (int j=0;j1][j+1]=change(theMap[i][j]) ;if (theMap[i][j]=='*') dp[i+1][j+1]=0 ;else if (theMap[i][j]=='@') {s=i+1;t=j+1;}}}for (int rnd=0;rndfor (int i=1;i<=n;i++){for (int j=1;j<=m;j++){if (a[i][j]==2) { //障碍物 continue ;} int cnt=0;for (int k=0;k<8;k++){int tx=i+dx[k],ty=j+dy[k] ;if (!check(tx,ty)) continue;tmp[++cnt]=dp[tx][ty] ; }sort(tmp+1,tmp+cnt+1) ;dp[i][j]=min(dp[i][j],min(tmp[1]+3,tmp[2]+1)) ;}}}if (dp[s][t]==0x3f3f3f3f) return -1 ;else return dp[s][t] ;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！