> 我的算法是把每个点拆成两个,[0]左脚踩和[1]右脚踩,然后连边,写了个最朴素的Dij求最短路：
> 
> long sx[2][9] = {1, 1, 1, 1, 1, 2, 2, 2, 3, -1, -1, -1, -1, -1, -2, -2, -2, -3};
> long sy[9] = {2, 1, 0, -1, -2, 1, 0, -1, 0};
> n=w*h;
> while (true) {
>                 k = n;
>                 k1 = 0;
>                 min = MAXIUM;
>                 for (i=0;i<n;++i) {
>                     for (j=0;j<2;++j) {
>                         if (!stat[i][j] && dis[i][j]<min) {
>                            k = i;
>                            k1 = j;
>                            min = dis[i][j];
>                         }
>                     }
>                 }
>                 if (k==n || t[k])
>                    break;
>                 stat[k][k1] = true;
>                 j1 = k1;
>                 k1 = (k1+1)%2;
>                 x = k%w;
>                 y = k/w;
>                 for (i=0;i<9;++i) {
>                     y1 = y+sy[i];
>                     x1 = x+sx[k1][i];
>                     if (x1>=0 && x1<w && y1>=0 && y1<h) {
>                        j = y1*w+x1;
>                        if (!stat[j][k1] && dis[j][k1]>dis[k][j1]+c[j]) {
>                           dis[j][k1] = dis[k][j1]+c[j];
>                        }
>                     }
>                 }
>           }
> 
> 结果TLE，TLE，又TLE，再TLE，还是TLE……
> 崩溃~后来写了个只在当前拓展过的节点中找最小值的（……多写了100+行），A了~600多MS。
> 感觉这题数据量不是很大，n=30*60=1800,最朴素的Dij也只不过O(n^2)，10^6而已，怎么会T呢？