UVA 10798 - Be wary of Roses

题目链接

题意：给定一个地图，人一开始在中心，问选择一种走法走出去，使得面朝任何一个方向走，踩到的花的最大值最小

思路：用优先队列进行BFS，每次取出踩到最少的情况，广搜记录状态为当前位置，和4个方向分别踩到的花数

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int N = 21; const int d[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}; int n, vis[N][N][11][11][11][11]; char g[N][N]; 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
      
        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)); } } } } int main() { while (~scanf("%d", &n) && n) { init(); printf("At most %d rose(s) trampled.\n", bfs()); } return 0; }