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

时间：2024-08-03 00:07:08

10798 - Be wary of Roses

You've always been proud of your prize rose garden. However, some jealous fellow gardeners will stop at nothing to gain an edge over you. They have kidnapped, blindfolded, and handcuffed you, and dumped you right in the middle of your treasured roses! You need to get out, but you're not sure you can do it without trampling any precious flowers.

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

Fortunately, you have the layout of your garden committed to memory. It is an N×N collection of square plots (N odd), some containing roses. You are standing on a square marble plinth in the exact center. Unfortunately, you are quite disoriented, and have no idea which direction you're facing! Thanks to the plinth, you can orient yourself facing one of North, East, South, or West, but you have no way to know which.

You must come up with an escape path that tramples the fewest possible roses, no matter which direction you're initially facing. Your path must start in the center, consist only of horizontal and vertical moves, and end by leaving the grid.

input

Every case begins with N, the size of grid ( 1UVA 10798 - Be wary of Roses （bfs+hash）NUVA 10798 - Be wary of Roses （bfs+hash）21), on a line. N lines with N characters each follow, describing the garden: `.' indicates a plot without any roses, `R' indicates the location of a rose, and `P' stands for the plinth in the center.

Input will end on a case where N = 0. This case should not be processed.

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。


思路：


开始用优先队列bfs，按照四个方向的最大step排序，二维坐标判重，WA了，想了一下，没有这么简单，因为坐标相同，step相同这样的状态也有优劣，在我贴的数据中能找到反例。


想了一下，由于地图不大，每个方向最多十步，可以把向每个方向走的步数存下来判重，所以这个方法可行，这样每个状态就是唯一等价的了，可以再开4维数组，我用了hash的思想压缩在一维中了，具体见代码。


代码：


#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <string>

#include <map>

#include <stack>

#include <vector>

#include <set>

#include <queue>

#pragma comment (linker,"/STACK:102400000,102400000")

#define maxn 22

#define MAXN 100005

#define mod 1000007

#define INF 0x3f3f3f3f

#define pi acos(-1.0)

#define eps 1e-6

typedef long long ll;

using namespace std;

int n,m,ans,flag,cnt;

char mp[maxn][maxn],pp[200];

bool vis[maxn][maxn][14650]; // 最后一维要比AAAA(11)大

int fac[]={1,11,121,1331};

int dx[]={-1,1,0,0};

int dy[]={0,0,-1,1};

struct Node

{

    int x,y;

    int a[4],step;

    bool operator <(const Node &xx)const

    {

        return step>xx.step;

    }

}cur,now;

void bfs()

{

    int i,j,t,nx,ny,tx,ty,step,h;

    memset(vis,0,sizeof(vis));

    priority_queue<Node>q;

    cur.x=cur.y=n/2;

    cur.step=0;

    memset(cur.a,0,sizeof(cur.a));

    vis[cur.x][cur.y][0]=1;

    q.push(cur);

    while(!q.empty())

    {

        now=q.top();

        q.pop();

        nx=now.x,ny=now.y;

//        printf("nx:%d ny:%d step:%d\n",nx,ny,now.step);

        for(i=0;i<4;i++)

        {

            tx=nx+dx[i];

            ty=ny+dy[i];

            if(tx<0||tx>=n||ty<0||ty>=n)

            {

                ans=now.step;

                return ;

            }

            cur.x=tx,cur.y=ty;

            cur.a[0]=now.a[0]+pp[mp[tx][ty]];

            cur.a[1]=now.a[1]+pp[mp[ty][n-1-tx]];

            cur.a[2]=now.a[2]+pp[mp[n-1-tx][n-1-ty]];

            cur.a[3]=now.a[3]+pp[mp[n-1-ty][tx]];

            step=0;

            h=0;

            for(j=0;j<4;j++)

            {

                h+=cur.a[j]*fac[j];

                step=max(step,cur.a[j]);

            }

            if(vis[tx][ty][h]) continue ;

            vis[tx][ty][h]=1;

            cur.step=step;

            q.push(cur);

        }

    }

}

int main()

{

    int i,j;

    pp['R']=1,pp['.']=pp['P']=0;

    while(scanf("%d",&n),n)

    {

        for(i=0;i<n;i++)

        {

            scanf("%s",mp[i]);

        }

        bfs();

        printf("At most %d rose(s) trampled.\n",ans);

    }

    return 0;

}

/*

9

RRRR.R.RR

RRRR.R.RR

R.RR.R.RR

RRRR.R.RR

RRRRPRRRR

RR.RRRRRR

RR.RR....

RR.RRRRRR

RR.RRRRRR

21

RRRRRRRR.RRRRRRRRRRRR

RRRRRRRR..RRRR...RRRR

RRRRR...R..RR..R.RRRR

RRRRR.R..R....R..RRRR

R...R..R..RRRR..RRRRR

R.R..R..R..RR..R...RR

R..R..R..R....R..R.RR

RR..R..R..RRRR..R..RR

RRR.RR.RR..RR..R..R..

RRR.RR.RRR.R..R..R..R

RR..R..R..P..R..R..RR

R..R..R..R.RRR.RR.RRR

..R..R..RR..RR.RR.RRR

RR..R..RRRR..R..R..RR

RR.R..R....R..R..R..R

RR...R..RR..R..R..R.R

RRRRR..RRRR..R..R...R

RRRR..R....R..R.RRRRR

RRRR.R..RR..R...RRRRR

RRRR...RRRR..RRRRRRRR

RRRRRRRRRRRR.RRRRRRRR

21

RRRRRRRR.RRRRRRRRRRRR

RRRRRRRR..RRRR...RRRR

RRRRR...R..RR..R.RRRR

RRRRR.R..RR...R..RRRR

R...R..R..RRRR..RRRRR

R.R..R..R..RR..R...RR

R..R..R..R....R..R.RR

RR..R..R..RRRR..R..RR

RRR.RR.RR..RR..R..R..

RRR.RR.RRR.R..R..R..R

RR..R..R..PR.R..R..RR

R..R..R..R.RRR.RR.RRR

..R..R..RR..RR.RR.RRR

RR..R..RRRR..R..R..RR

RR.R..R....R..R..R..R

RR...R..RR..R..R..R.R

RRRRR..RRRR..R..R...R

RRRR..R....R..R.RRRRR

RRRR.R..RR..R...RRRRR

RRRR...RRRR..RRRRRRRR

RRRRRRRRRRRRRRRRRRRRR

21

RRRRRRRR.RRRRRRRRRRRR

.RRRRRRR..RRRR...RRRR

..RRR...R..RR.RR.RRRR

...RR.RRRR....RRRRRRR

....R..RR.RRRR..RRRRR

.....R..R..RR..R...RR

......R..R....RR.RRRR

.......R..RRRR..R..RR

........R..RR.RR..R..

.........R.R..R..R..R

..........P..R..R..RR

.........R.RRR.RR.RRR

........RR.RR..RR.RRR

.......RRRR..R..R..RR

......RRR..R..R..R..R

.....R.RRR..R..RR.RRR

....R..RRRR..R..R...R

...R..RR...RR.R.RRRRR

..RR.R..RR..R...RRRRR

.RRR.R.RRRR..RRRRRRRR

RRRRRRRRRRRR.RRRRRRRR

21

.................R.R.

RRRRRRRRRRRRRRRRRR.R.

.................R.R.

RRRRRRRRRRRRRRRR.R.R.

.R.............R.R.R.

.R.RRRRRRRRRRR.R.R.R.

.R.R.........R.R.R.R.

.R.R.RRRRRRR.R.R.R.R.

.R.R.R.....R.R.R.R.R.

.R.R.R.RRR.R.R.R.R.R.

.R.R.R.R..P..R.R.R.R.

.R.R.R.R.R.RRR.R.R.R.

.R.R.R.R.R.....R.R.R.

.R.R.R.R.RRRRRRR.R.R.

.R.R.R.R.........R.R.

.R.R.R.RRRRRRRRRRR.R.

.R.R.R.............R.

.R.R.RRRRRRRRRRRRRRRR

.R.R.................

.R.RRRRRRRRRRRRRRRRRR

.R.R.................

21

.................R.R.

RRRRRRRRRRRRRRRRRR.R.

.................R.R.

RRRRRRRRRRRRRRRR.R.R.

...............R.R.R.

...RRRRRRRRRRR.R.R.R.

.............R.R.R.R.

.....RRRRRRR.RRRRRRR.

.....R.....R.R.R.R.R.

.......RRR.R.R.R.R.R.

..........P..R.R.R.R.

.........R.RRR.R.R.R.

.........R.....R.R.R.

.......R.RRRRRRR.R.R.

.......R..R......R.R.

.......RRRRRRRRRRR.R.

.....R....R........R.

.....RRRRRRRRRRRRRRRR

.....................

...RRRRRRRRRRRRRRRRRR

.R.R.................

21

.................R.R.

RRRRRRRRRRRRRRRRRR.R.

................RR.R.

RRRRRRRRRRRRRRRRRR.R.

...............RRRRR.

...RRRRRRRRRRR.RRRRR.

.............R.RRR.R.

.....RRRRRRR.RRRRRRR.

.....R.....R.R.R.R.R.

.......RRR.R.R.R.R.R.

..........P..R.R.R.R.

.........R.RRR.R.R.R.

.RR......R.....R.R.R.

.RR....R.RRRRRRR.R.R.

.RR....R..R......R.R.

.RR....RRRRRRRRRRR.R.

.RR..R....R........R.

.....RRRRRRRRRRRRRRRR

.....RR..............

...RRRRRRRRRRRRRRRRRR

.R.R.................

21

RRRRRRRRRR.RRRRRRRRRR

RRRRRRRRRR..RRRRRRRRR

RRRRRRRRRR.RRRRRRRRRR

RRRRRRRRRR..RRRRRRRRR

RRRRRRRRRR.RRRRRRRRRR

RRRRRRRRR.RRRRRRRRRRR

RRRRRRRRRRRRRRRRRRRRR

RRRRRRRRR.RRRRRRRRRRR

RRRRRRRRRRRRRRRRRRRRR

R.R.RRRRR...R.R.RRRRR

RRRR......P......RRRR

RRRRR.R.R...RRRRR.R.R

RRRRRRRRRRRRRRRRRRRRR

RRRRRRRRRRR.RRRRRRRRR

RRRRRRRRRRRRRRRRRRRRR

RRRRRRRRRRR.RRRRRRRRR

RRRRRRRRRR.RRRRRRRRRR

RRRRRRRRR..RRRRRRRRRR

RRRRRRRRRR.RRRRRRRRRR

RRRRRRRRR..RRRRRRRRRR

RRRRRRRRRR.RRRRRRRRRR

0

ans:3 0 1 2 0 2 3 4

*/

相关文章