UVa 10047，独轮车

题目链接：https://uva.onlinejudge.org/external/100/10047.pdf

题目链接：http://vjudge.net/contest/132239

《训练指南》P308

没什么好说的，学习一下刘汝佳的风格。

#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3fint R,C;
const int maxr =  + ;
const int maxc =  + ;
char maze[maxr][maxc];
int sr,sc,tr,tc;
int ans;struct State {
    int r,c,dir,color;
    State(int r,int c,int dir,int color) : r(r),c(c),dir(dir),color(color) {}
};const int dr[] = {-,,,};
const int dc[] = {,-,,};
int d[maxr][maxc][][],vis[maxr][maxc][][];queue <State> Q;void update (int r,int c,int dir,int color,int v)
{
    if(r<||r>=R||c<||c>=C) return;
    if(maze[r][c]=='.'&&!vis[r][c][dir][color])
    {
        Q.push(State(r,c,dir,color));
        vis[r][c][dir][color] = ;
        d[r][c][dir][color] = v;
        if(r==tr&&c==tc&&color==) ans = min(ans,v);
    }
}void bfs(State st)
{
    Q.push(st);
    d[st.r][st.c][st.dir][st.color] = ;
    vis[st.r][st.c][st.dir][st.color] = ;
    while(!Q.empty())
    {
        st = Q.front(); Q.pop();
        int v = d[st.r][st.c][st.dir][st.color] + ;
        update (st.r,st.c,(st.dir+)%, st.color, v);
        update (st.r,st.c,(st.dir+)%, st.color, v);
        update (st.r+dr[st.dir],st.c + dc[st.dir],st.dir,(st.color+)%,v);
    }
}int main()
{
    int cases = ;
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&R,&C),R)
    {
        for(int i=;i<R;i++)
        {
            scanf("%s",maze[i]);
            {
                for(int j=;j<C;j++)
                {
                    if(maze[i][j]=='S')
                    {
                        sr = i;
                        sc = j;
                    }
                    else if(maze[i][j]=='T')
                    {
                        tr = i;
                        tc = j;
                    }
                }
            }
        }        maze[sr][sc] = maze[tr][tc] = '.';
        ans = INF;
        memset(vis,,sizeof(vis));
        bfs(State(sr,sc,,));
        if(cases>) printf("\n");
        printf("Case #%d\n",++cases);
        if(ans==INF) printf("destination not reachable\n");
        else printf("minimum time = %d sec\n", ans);
    }
    return ;
}