【動態規劃】抄近路
時間限制: 1 Sec 內存限制: 64 MB
提交: 105 解決: 68
[提交] [狀態] [命題人:admin]
題目描述
“最近不知道怎么回事，感覺我們這個城市變成了一個神奇的地方，有時在路上走著走著人就消失了！走著走著突然又有人出現了！你以為這是《寂靜嶺》，《生化危機》，《行尸走肉》拍攝地？……哎，先不說了，這該死的霧霾又讓我們迷路了。”李旭琳發愁地說。

張琪曼和李旭琳每天要從家到車站，小區被道路分成許多正方形的塊，共有N×M塊。由于道路太多以及霧霾的影響，她們總是迷路，所以你需要幫她們計算一下從家到車站的最短距離。注意，一般情況下，小區內的方塊建有房屋，只能沿著附近的街道行走，有時方塊表示公園，那么就可以直接穿過。

輸入
第一行是N和M（0<N，M≤1000）。注意，李旭琳家坐標在方塊（1，1）的西南角，車站在方塊（M，N）的東北角。每個方塊邊長100米。接下來一行是整數K，表示可以對角線穿過的方塊坐標，然后有K行，每行是一個坐標。

輸出
輸出最短距離，四舍五入到整數米。

樣例輸入
復制樣例數據
3 2
3
1 1
3 2
1 2
樣例輸出
383

解題思路：i
已知可以走的方向有上、下、左、右，且有的方塊允許走對角線，因此可以用$dp[i][j]$代表做到坐標為$(i,j)$位置所走的最小路程，因此此時僅需先判斷其上一步是否能到達，再更新$dp[i][j]即可$：
$dp[i][j]=min(dp[i][j],dp[i?1][j]+100.0)$從左面到達$(i,j)$
$dp[i][j]=min(dp[i][j],dp[i][j?1]+100.0)$從下面到達$(i,j)$
$dp[i][j]=min(dp[i][j],dp[i+1][j]+100.0)$從右面到達$(i,j)$
$dp[i][j]=min(dp[i][j],dp[i][j+1]+100.0)$從上面到達$(i,j)$
$dp[i][j]=min(dp[i][j],dp[i?1][j?1]+100.0?sqrt(2.0))$從左下角到達$(i,j)$
$dp[i][j]=min(dp[i][j],dp[i?1][j+1]+100.0?sqrt(2.0))$從右下角到達$(i,j)$
$dp[i][j]=min(dp[i][j],dp[i+1][j?1]+100.0?sqrt(2.0))$從左上角到達$(i,j)$
$dp[i][j]=min(dp[i][j],dp[i+1][j+1]+100.0?sqrt(2.0))$從右上角到達$(i,j)$

代碼：

//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
double dp[1200][1200];
bool vis[1200][1200];
bool can[1200][1200];
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);//ios::sync_with_stdio(0),cin.tie(0);int m,n;scanf("%d %d",&n,&m);int k;scanf("%d",&k);rep(i,0,n) {rep(j,0,m) {dp[i][j]=inf;}}dp[0][0]=0;rep(i,1,k) {int a,b;scanf("%d %d",&a,&b);can[a][b]=true;}vis[0][0]=true;rep(i,0,n) {rep(j,0,m) {if(vis[i-1][j]) dp[i][j]=min(dp[i][j],dp[i-1][j]+100.0);if(vis[i][j-1]) dp[i][j]=min(dp[i][j],dp[i][j-1]+100.0);if(vis[i+1][j]) dp[i][j]=min(dp[i][j],dp[i+1][j]+100.0);if(vis[i][j+1]) dp[i][j]=min(dp[i][j],dp[i][j+1]+100.0);if(vis[i-1][j-1]&&can[i][j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]+100.0*sqrt(2.0));if(vis[i-1][j+1]&&can[i][j+1]) dp[i][j]=min(dp[i][j],dp[i-1][j+1]+100.0*sqrt(2.0));if(vis[i+1][j-1]&&can[i+1][j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]+100.0*sqrt(2.0));if(vis[i+1][j+1]&&can[i+1][j+1]) dp[i][j]=min(dp[i][j],dp[i+1][j+1]+100.0*sqrt(2.0));vis[i][j]=true;//cout<<i<<" "<<j<<" "<<(int)dp[i][j]<<endl;}}printf("%.f\n",dp[n][m]);return 0;
}