soj1135 飞越原野

/**
 *  原题：http://222.200.185.45/1135
 *  看了题解：http://www.cnblogs.com/ciel/archive/2013/01/25/2876806.html
 *  代码写得风格比较容易接受，说回题目。。。
 *  我看这道题时还蛮蛋疼的，没有想到如何将状态空间增加一个维度，
 *      看完代码后觉得是一件比较容易理解的事情，
 *      以后在思考搜索问题时要注意搜索状态的设计！
 */

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 105;

struct state
{
    int x, y, dis, remain;
    state(int x, int y, int d, int r):
        x(x), y(y), dis(d), remain(r) { }
};

int mx[4] = {-1, 0, 1, 0};
int my[4] = {0, 1, 0, -1};

//  由于状态空间维度上升，visit数组相应维度上升1
bool graph[MAX][MAX];
bool visit[MAX][MAX][MAX];
int m, n, d;

bool inGraph(int x, int y)
{
    return x >= 0 && x < m && y >= 0 && y < n;
}

void bfs()
{
    memset(visit, false, sizeof(visit));
    queue<state> q;
    q.push(state(0, 0, 0, d));
    visit[0][0][d] = true;
    while(!q.empty())
    {
        state temp = q.front(); q.pop();

        if(temp.x == m-1 && temp.y == n-1)
        {
            cout << temp.dis << endl;
            return;
        }

        for(int i = 0; i < 4; ++ i)
        {
            int nx = temp.x + mx[i];
            int ny = temp.y + my[i];

            //  graph[i][j] = true
            if(inGraph(nx, ny) && graph[nx][ny] && !visit[nx][ny][temp.remain])
            {
                q.push(state(nx, ny, temp.dis+1, temp.remain));
                visit[nx][ny][temp.remain] = true;
            }

            // flying no matter 'P' or 'L'
            for(int j = 1; j < temp.remain; ++ j)
            {
                nx += mx[i];
                ny += my[i];
                //  only landing on plane
                if(inGraph(nx, ny) && graph[nx][ny] && !visit[nx][ny][temp.remain-j-1])
                {
                    q.push(state(nx, ny, temp.dis+1, temp.remain-j-1));
                    visit[nx][ny][temp.remain-j-1] = true;
                }
            }
        }
    }
    cout << "impossible" << endl;
}

int main()
{
    freopen("data.in", "r", stdin);
    char temp;
    cin >> m >> n >> d;

    memset(graph, false, sizeof(graph));
    for(int i = 0; i < m; ++ i)
        for(int j = 0; j < n; ++ j)
        {
            cin >> temp;
            graph[i][j] = temp == 'P';
        }

    bfs();
    return 0;
}