103北市賽 4.太空迷走 (Astro)

想法：

DP題。
要記錄的狀態有[剩餘能量f，座標p，當前前進方向w]，
轉移的話有dp ( f, p, w ) = min ( dp ( f, p+w, w ) , dp ( f+1, p+其他方向, w) ) + 1，
然後枚舉到終點前的最後一次轉彎，同時更新最佳解。
有點不太懂它給已知最佳解要幹嘛= =。
有些邊界條件不太確定，
但是沒有judge可以傳，範測也過了，
於是乎我就當它是對的吧>///<。

Code：

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <utility>
#define INF 1e9
using namespace std;
int mp[105][105];
int dp[15][105][105][4];
struct st{int f,x,y,way;} par[15][105][105][4];
int s[105][105];
int dx[]={0,1,-1,0};
int dy[]={1,0,0,-1};
int n,m,pwr;
int sx,sy,tx,ty;
double expect;
int get(int f,int x,int y,int way)//time of, f power remain
{
    if(f<=0||f>=pwr||x<=0||x>n||y<=0||y>m||mp[x][y])
        return INF;
    if(~dp[f][x][y][way])
        return dp[f][x][y][way];
    dp[f][x][y][way]=INF;
    for(int i=0;i<4;i++)
        if(dp[f][x][y][way]>get(f+(i!=way),x-dx[i],y-dy[i],i)+1)
        {
            dp[f][x][y][way]=get(f+(i!=way),x-dx[i],y-dy[i],i)+1;
            par[f][x][y][way]=st{f+(i!=way),x-dx[i],y-dy[i],i};
        }
    return dp[f][x][y][way];
}
void init();
void sol();
vector<pair<int,int>> ans;
void trace(int f,int x,int y,int way)
{
    if(!f)
        return;
    auto p=par[f][x][y][way];
    trace(p.f,p.x,p.y,p.way);
    if(p.way!=way)
        ans.push_back(make_pair(x,y));
}
inline int sum(int a,int b,int c,int d)
{return s[a][b]-s[c-1][b]-s[a][d-1]+s[c-1][d-1];}
int main()
{
    scanf("%d%d",&sx,&sy);
    sx++,sy++;
    scanf("%d%d",&tx,&ty);
    tx++,ty++;
    scanf("%d",&pwr);
    scanf("%lf",&expect);
    scanf("%d%d",&n,&m);
    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++)
            scanf("%d",&mp[i][j]);
    init();
    sol();
    return 0;
}
void sol()
{
    if(sx==tx||sy==ty){/*todo*/}
    double best=INF;
    for(int f=1;f<pwr;f++)
        for(int i=0;i<4;i++)
            for(int j=1;j<=max(n,m);j++)
            {
                int nx=tx+dx[i]*j;
                int ny=ty+dy[i]*j;
                if(nx<=0||nx>n||ny<=0||ny>m)
                    continue;
                if(mp[nx][ny]||sum(nx,ny,tx,ty))
                    continue;
                for(int k=0;k<4;k++)
                    if(best>get(f,nx,ny,k)+(double)j/f)
                    {
                        best=get(f,nx,ny,k)+(double)j/f;
                        ans.clear();
                        trace(f,nx,ny,k);
                        if(*ans.rbegin()!=make_pair(nx,ny))
                            ans.push_back(make_pair(nx,ny));
                        ans.push_back(make_pair(tx,ty));
                    }
            }
    for(auto it=ans.begin();it!=ans.end();it++)
        if(*it==make_pair(sx,sy))
            ans.erase(it);
    printf("%d\n",ans.size());
    for(auto e:ans)
        printf("%d %d\n",e.first-1,e.second-1);
}
void init()
{
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            dp[pwr-1][sx][sy][j]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+mp[i][j];
}