DesertWind TopCoder - 1570
2024-09-01 00:39:41
分析
首先我们要知道为了情况最坏,无论你到哪,一定会在你前往绿洲的最短路上的那片沙子上刮风,所以这个点到绿洲的最短路即为他相连的点中到绿洲距离最短的距离+3和次短的距离+1的最小值,具体实现见代码。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define sp cout<<"---------------------------------------------------"<<endl;
const int inf=0x3f3f3f3f;
const int dx[]={-,,,-,,-,,},dy[]={-,-,-,,,,,};
class DesertWind {
public:
int a[][],ans[][],n,m;
bool is(int x,int y){
if(x<||y<||x>n||y>m||a[x][y]==inf)return false;
return true;
}
int daysNeeded(vector<string>theMap){
n=theMap.size(),m=theMap[].length();
int i,j,sx,sy,k;
memset(ans,0x3f,sizeof(ans));
memset(a,0x3f,sizeof(a));
for(i=;i<n;i++)
for(j=;j<m;j++)
if(theMap[i][j]=='@')sx=i+,sy=j+,a[i+][j+]=;
else if(theMap[i][j]=='-')a[i+][j+]=;
else if(theMap[i][j]=='*'){
a[i+][j+]=;
ans[i+][j+]=;
}
for(int _=;_<=n*m;_++)
for(i=;i<=n;i++)
for(j=;j<=m;j++)
if(a[i][j]!=inf){
int cnt=,d[];
for(k=;k<=;k++)d[k]=inf;
for(k=;k<;k++){
int x=i+dx[k],y=j+dy[k];
if(is(x,y))d[++cnt]=ans[x][y];
}
sort(d+,d+cnt+);
ans[i][j]=min(ans[i][j],min(d[]+,d[]+));
}
return ans[sx][sy]==inf?-:ans[sx][sy];
}
};
最新文章
- objective-c 语法快速过(2)
- C#反射机制 Type类型
- Creating Classes 创建类
- Buffer Overflow Study
- Python pycurl
- mysq优化参数详解:innodb_buffer_pool_size,innodb_file_per_table
- 学习使用Et采集的过程和分析
- day52
- C#之再议数组和集合
- .net Work Flow 4.0
- hdu4699 Editor 2013 多校训练第十场 D题 数列维护 splay | 线段树 | 栈!!!!!
- storm的并发机制
- devexpress实现单元格合并以及依据条件合并单元格
- 流程控制语句if、else、elif、break、continue
- Python3.0科学计算学习之绘图(四)
- 微信小程序的MVVM思想
- unity室内外VR漫游
- springboot使用redisTemplate遇到的问题
- 金九银十,史上最强 Java 面试题整理。
- 对象的宽度、top位置,x坐标属性