UVA 10798 - Be wary of Roses （bfs+hash）

参考http://blog.csdn.net/tobewhatyouwanttobe/article/details/17403987和http://blog.csdn.net/accelerator_/article/details/38901669

output

For each case, output a line containing the minimum guaranteed number of roses you can step on while escaping.

5
.RRR.
R.R.R
R.P.R
R.R.R
.RRR.
0

At most 2 rose(s) trampled.

题意：

UVA的题就是不好读懂呀，我会说我搞了两个小时才看懂题意么?

意思就是 让你确定一条方案 这个方案保证无论你开始面朝哪个方向，用这个方案走出去后使得踩到的玫瑰最小。如样例（上、上、上 这个方案就能保证你开始无论朝那个方向，这样走踩到的玫瑰最小为2），方便理解，解释一下我贴的第一组样例，这个样例 就可以确定 “上、上、左、左、左、左、左 ” 这个方案使得答案最优为 3。

要点：看到能够存的下，就存，，然后用旋转的原理；、

if (g[xx][yy] == 'R') up++;  
            if (g[n - 1 - yy][xx] == 'R') left++;  
            if (g[n - 1 - xx][n - 1 - yy] == 'R') down++;  
            if (g[yy][n - 1 - xx] == 'R') right++;  

struct State {  
    int x, y, val;  
    int up, left, down, right;  
    State() {x = y = up = left = down = right = 0;}  
    State(int x, int y, int up, int left, int down, int right) {  
        this->x = x;  
        this->y = y;  
        this->up = up;  
        this->left = left;  
        this->down = down;  
        this->right = right;  
        val = max(max(max(up,left), down), right);  
    }  
    bool operator < (const State& c) const {  
        return val > c.val;  
    }  
} s;  

void init() {  
    for (int i = 0; i < n; i++) {  
        scanf("%s", g[i]);  
        for (int j = 0; j < n; j++)  
            if (g[i][j] == 'P')  
                s.x = i, s.y = j;  
    }  
}  

int bfs() {  
    memset(vis, 0, sizeof(vis));  
    priority_queue<State> Q;  
    Q.push(s);  
    vis[s.x][s.y][0][0][0][0] = 1;  
    while (!Q.empty()) {  
        State u = Q.top();  
        Q.pop();  
        if (u.x == 0 || u.x == n - 1 || u.y == 0 || u.y == n - 1) return u.val;  
        for (int i = 0; i < 4; i++) {  
            int xx = u.x + d[i][0];  
            int yy = u.y + d[i][1];  
            int up = u.up;  
            int left = u.left;  
            int down = u.down;  
            int right = u.right;  
            if (g[xx][yy] == 'R') up++;  
            if (g[n - 1 - yy][xx] == 'R') left++;  
            if (g[n - 1 - xx][n - 1 - yy] == 'R') down++;  
            if (g[yy][n - 1 - xx] == 'R') right++;  
            if (!vis[xx][yy][up][left][down][right]) {  
                vis[xx][yy][up][left][down][right] = 1;  
                Q.push(State(xx, yy, up, left, down, right));  
            }  
        }  
    }  
}