飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3890

题意：有个人站在(0,0)位置，然后给你n*n的地图，其中地图中有黄金，怪物，坑，平地，因为题目简化了，坑不能进，怪物的地方不能进，黄金只有1块。人物的动作可以是转向，向前，挖金子，从(0,0)点出来，其中每个动作要花费10点的值，黄金值1000点值。求出来之后最大的值是多少.

分析：一看n<=20，且方向就只有4个，那么可以建立vis[20][20][4]的数组进行BFS模拟。

(1)由于数据非常小，所以我考虑到一点事情，就是如果黄金在sx,sy上，然后我们到达sx,sy,方向为1的值和到达sx,sy方向为2的值相同，然后从1到(0,0）比从2到(0,0)慢，那么如果我们到达1的时候就结束BFS，那么答案就错了，所以我是枚举到达sx,sy四个方向的值，然后再从这四个方向继续BFS回到(0,0)，然后求出最小值就好，其中一些细节不符合条件的直接输出-1就好。虽然代码有点长，但是也不是特边复杂

（2）可以直接打标记，就是假设黄金在sx，sy，如果到了sx，sy，那么直接标记拿到了黄金，最后到了(0,0)之后，如果拿到了黄金那么就是最优值，这样代码就边的比较短了

最后啪啪啪就可以AC了。

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
struct he
{
    int x,y,d,val;
};
const int maxn=2*12;
int ai[maxn][maxn];
bool vis[maxn][maxn][5];
int n,T;
int ex,ey;
void init()
{
    scanf("%d",&n);
    memset(ai,0,sizeof(ai));
    for(int i=0; i<=n; i++)ai[0][i]=ai[i][0]=ai[n+1][i]=ai[i][n+1]=2;
    int u,v,w;
    while(scanf("%d%d%d",&u,&v,&w)!=EOF&&u!=-1)
    {

        v++;
        w++;
        if(u==3)
        {
            ex=v;
            ey=w;
        }
        ai[v][w]=u;
    }
}
pair<int,int> calD(int d,int x,int y)
{
    if(d==1)return make_pair(x+1,y);
    if(d==2)return make_pair(x,y+1);
    if(d==3)return make_pair(x-1,y);
    if(d==4)return make_pair(x,y-1);
}
int BFS1(int dd)
{
    memset(vis,0,sizeof(vis));
    queue<he> Q;
    Q.push((he)
    {
        1,1,1,0
    });
    vis[1][1][1]=1;
    while(!Q.empty())
    {
        he now=Q.front();
        Q.pop();
        int nx=now.x;
        int ny=now.y;
        int nd=now.d;
        int nv=now.val;
        if(ai[nx][ny]==3&&nd==dd)
        {
            return nv;
        }
        pair<int,int> need=calD(nd,nx,ny);
        int x=need.first;
        int y=need.second;
        if(ai[x][y]!=1&&ai[x][y]!=2&&!vis[x][y][nd])
        {
            vis[x][y][nd]=1;
            Q.push((he)
            {
                x,y,nd,nv+10
            });
        }
        int d=nd+1;
        if(d==5)d=1;
        if(!vis[nx][ny][d])
        {
            vis[nx][ny][d]=1;
            Q.push((he)
            {
                nx,ny,d,nv+10
            });
        }
        d=nd-1;
        if(d==0)d=4;
        if(!vis[nx][ny][d])
        {
            vis[nx][ny][d]=1;
            Q.push((he)
            {
                nx,ny,d,nv+10
            });
        }
    }
    return -1;

}
int BFS2(int x1,int y1,int dd)
{
    memset(vis,0,sizeof(vis));
    vis[x1][y1][dd]=1;
    queue<he> Q;
    Q.push((he)
    {
        x1,y1,dd,0
    });
    while(!Q.empty())
    {
        he now=Q.front();
        Q.pop();
        int nx=now.x;
        int ny=now.y;
        int nd=now.d;
        int nv=now.val;
        if(nx==1&&ny==1)
        {
            return nv;
        }
        pair<int,int> need=calD(nd,nx,ny);
        int x=need.first;
        int y=need.second;
        if(ai[x][y]!=1&&ai[x][y]!=2&&!vis[x][y][nd])
        {
            vis[x][y][nd]=1;
            Q.push((he)
            {
                x,y,nd,nv+10
            });
        }
        int d=nd+1;
        if(d==5)d=1;
        if(!vis[nx][ny][d])
        {
            vis[nx][ny][d]=1;
            Q.push((he)
            {
                nx,ny,d,nv+10
            });
        }
        d=nd-1;
        if(d==0)d=4;
        if(!vis[nx][ny][d])
        {
            vis[nx][ny][d]=1;
            Q.push((he)
            {
                nx,ny,d,nv+10
            });
        }
    }
    return -1;

}
void play()
{
    if(ai[1][1]==1||ai[1][1]==2)
    {
        printf("-1\n");
        return;
    }
    int MAX=-1;
    for(int i=1; i<=4; i++)
    {
        int ng=BFS1(i);
        if(ng==-1)
        {
            printf("-1\n");
            return;
        }
        int nb=BFS2(ex,ey,i);
        MAX=max(MAX,1000-20-nb-ng);

    }
    printf("%d\n",MAX);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
struct he
{
    int x,y,d,val,reach;
};
const int maxn=2*12;
int ai[maxn][maxn];
bool vis[maxn][maxn][5][2];
int n,T;
int ex,ey;
void init()
{
    scanf("%d",&n);
    memset(ai,0,sizeof(ai));
    for(int i=0; i<=n; i++)ai[0][i]=ai[i][0]=ai[n+1][i]=ai[i][n+1]=2;
    int u,v,w;
    while(scanf("%d%d%d",&u,&v,&w)!=EOF&&u!=-1)
    {

        v++;
        w++;
        if(u==3)
        {
            ex=v;
            ey=w;
        }
        ai[v][w]=u;
    }
}
pair<int,int> calD(int d,int x,int y)
{
    if(d==1)return make_pair(x+1,y);
    if(d==2)return make_pair(x,y+1);
    if(d==3)return make_pair(x-1,y);
    if(d==4)return make_pair(x,y-1);
}
int BFS1()
{
    memset(vis,0,sizeof(vis));
    queue<he> Q;
    Q.push((he)
    {
        1,1,1,0,0
    });
    vis[1][1][1][0]=1;
    while(!Q.empty())
    {
        he now=Q.front();
        Q.pop();
        int nx=now.x;
        int ny=now.y;
        int nd=now.d;
        int nv=now.val;
        int reach=now.reach;
        if(nx==1&&ny==1&&reach==1)return nv;
        if(ai[nx][ny]==3)
        {
            reach=1;
        }
        pair<int,int> need=calD(nd,nx,ny);
        int x=need.first;
        int y=need.second;
        if(ai[x][y]!=1&&ai[x][y]!=2&&!vis[x][y][nd][reach])
        {
            vis[x][y][nd][reach]=1;
            Q.push((he)
            {
                x,y,nd,nv+10,reach
            });
        }
        int d=nd+1;
        if(d==5)d=1;
        if(!vis[nx][ny][d][reach])
        {
            vis[nx][ny][d][reach]=1;
            Q.push((he)
            {
                nx,ny,d,nv+10,reach
            });
        }
        d=nd-1;
        if(d==0)d=4;
        if(!vis[nx][ny][d][reach])
        {
            vis[nx][ny][d][reach]=1;
            Q.push((he)
            {
                nx,ny,d,nv+10,reach
            });
        }
    }
    return -1;

}
void play()
{
    if(ai[1][1]==1||ai[1][1]==2)
    {
        printf("-1\n");
        return;
    }
    int MAX=-1;
    int val=BFS1();
    if(val==-1)printf("-1\n");
    else
    {
        MAX=max(MAX,1000-20-val);
        printf("%d\n",MAX);
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}