DP_ural_Metro

因为是图论专题，所以最初想到的是最短路，但是图怎么存？图的最短路需要保存可以经过的点(n*m个点10^6)，肯定爆了，不可能只保存交叉点。果断放弃。

考虑用DP

设当前在(i+1,j+1)表示到达这个点的最短距离。可以到达这里的点有三个。
则(i+1,j+1)=min( (i+1,j)+1，(i,j+1)+1，(i,j)+sqrt(2) )   ->   如果有交叉线。
初始状态是矩阵左边 和下边的边界，即(0,i)=(i,0)=i

思考

假设从行开始遍历，再求出到达该行的每一列的距离，则这里当i+1行求出来后，i就没用了.
所以每次只需要维护到达所有列的最短距离就可以了。

完整代码 : https://github.com/Iytz/algorithm/blob/master/graph/dp_1C.cpp

核心部分:

    for (int r=1; r<=m; ++r) {
        double NOupdate = d[0];
        d[0] += 1.0; 
        for (int c=1; c<=n; ++c){
            double save = d[c];
            if(has[r][c]) d[c]=NOupdate+sqrt(2);
            else d[c]=min(d[c-1],d[c])+1;
            NOupdate = save;
        }
    }