Rescue OJ （拯救被困的天使)

迈不过友情╰ 2022-08-27 15:52 187阅读 0赞

有个鸟人不小心被坏蛋抓到了，关进了一个矩形监狱，坏蛋派他的小弟看着鸟人，当然小弟可能很多，也可能小弟偷懒出去玩了；不管怎么样鸟人的朋友决定去救他，现在你手上有一副当前的监狱状态图，请你判断鸟人的朋友能不能救出他，若能请输出最小时间，若不能请输出“ .....”.他的朋友一分钟只能走一格，遇见坏蛋的小弟还要花一分钟打败小弟。

题目梳理：

题目中用优先序列最省脑子，但是咱不能只为省脑子做题不是；但还是说优先序列吧！bfs就是找最短路径用的，但是因为遇到了特殊情况，所以bfs就要特殊处理了，按bfs的思想当前走的步数最少的先进行遍历，so就用上优先队列了、、、、、

#include <stdio.h>
    #include <iostream>
    #include <queue>
    #include <functional>
    #define N 205
    using namespace std;
    char map[N][N];
    int n,m;
    struct sta 
    {
    	 int x,y,step;
     	 friend bool operator<(sta a,sta b)//与队列稍有不同的地方 ，具体其他的请见其他文章 
    	 { return a.step>b.step;}
    }A;
    int mov[4][2]={1,0,0,1,-1,0,0,-1};
    int  p_bfs()
    {
    	priority_queue<sta> q;//声明的时候要加上priority的 
    	while(!q.empty())q.pop();
    	sta cur,next;
    	q.push(A);
    	while(!q.empty())
    	{
    		cur=q.top();//是top，不是front 
    		q.pop();
    		for(int i=0;i<4;i++)
    		{
    			next.x=cur.x+mov[i][0];
    			next.y=cur.y+mov[i][1];
    			next.step=cur.step+1;
    			if(map[next.x][next.y]=='r')return next.step;
    			if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&map[next.x][next.y]!='#')
    			{
    				if(map[next.x][next.y]=='x')++next.step;
    				q.push(next);
    				map[next.x][next.y]='#';
    			}
    		}
    	}
    	return 0;
    }
    int main()
    {
    	while(scanf("%d%d",&n,&m)==2)
    	{
    		for(int i=0;i<n;i++)
    		for(int j=0;j<m;j++)
    		{
    			scanf(" %c",&map[i][j]);
    			if(map[i][j]=='a'){A.x=i;A.y=j;A.step=0;}
    		}
    		int sign=p_bfs();
    		if(sign)printf("%d\n",sign);
    		else
    		printf("Poor ANGEL has to stay in the prison all his life.\n");
    	}
    }

看到了一位牛人自己写的queue，不仅佩服，就顺便贴在后面了    地址： [http://blog.sina.com.cn/s/blog\_626631420100ticb.html][http_blog.sina.com.cn_s_blog_626631420100ticb.html]

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define SIZE 100000
    typedef struct { int x,y;} node;
    typedef struct { node base[SIZE]; int front,rear;} queue;
    queue Q;
    void push(node e)
    {
        Q.base[Q.rear].x = e.x;
        Q.base[Q.rear].y = e.y;
        Q.rear = (Q.rear+1)%SIZE;
    }
    node pop()
    {
        node e;
        e.x = Q.base[Q.front].x;
        e.y = Q.base[Q.front].y;
        Q.front = (Q.front + 1)%SIZE;
        return e;
    }
    const int INF = 999999;
    char map[220][220];
    int N,M;
    int find[220][220];
    int iPlus[4] = {-1,0,1,0};
    int jPlus[4] = {0,-1,0,1};
    void BFS(node start)
    {
        int k;
        Q.rear = 0;
        Q.front = 0;
        push(start);       
        node next,pre;
        find[start.x][start.y] = 0;
        while ( Q.rear!=Q.front )
        {
            pre = pop();
            for ( k = 0; k < 4; k++)
            {
                next.x = pre.x + iPlus[k];
                next.y = pre.y + jPlus[k];
                if ( next.x >= 1 && next.x <= N && next.y >= 1 && next.y <= M)
                {
                    if ( map[next.x][next.y] != '#' )
                    {       
                        if (map[next.x][next.y]!='x')
                        {           
                            if(find[next.x][next.y] >= find[pre.x][pre.y]+1)
                            {
                                find[next.x][next.y] = find[pre.x][pre.y]+1;
                                push(next);
                            }
                        }
                        else
                        {
                            if (find[next.x][next.y] >= find[pre.x][pre.y]+2)
                            {
                                find[next.x][next.y] = find[pre.x][pre.y]+2;
                                push(next);
                            }
                        }
                    }
                }
            }
           
        }
    }
    int main()
    {
        freopen("Sample Input.txt","r",stdin);
        system("Color F0");
        int i,j;char ch;
        node s,e;
        while ( scanf("%d%d",&N,&M)!=EOF)
        {
            getchar();
            for ( i = 1; i <= N; i++)
            {
                for ( j = 1; j <= M; j++)
                {
                    scanf("%c",&ch);
                    if ( ch=='r') { s.x = i; s.y = j;}
                    if ( ch=='a') { e.x = i; e.y = j;}
                    map[i][j] = ch;
                }
                getchar();
            }
            for ( i = 1; i <= N; i++)
            {
                for (j = 1; j <= M; j++)
                {
                    find[i][j] = INF;
                }
            }
            BFS(s);
            if (find[e.x][e.y]<INF)
                printf("%d\n",find[e.x][e.y]);
            else
                printf("Poor ANGEL has to stay in the prison all his life.\n");
        }
        getch();
        return 0;
    }

[http_blog.sina.com.cn_s_blog_626631420100ticb.html]: http://blog.sina.com.cn/s/blog_626631420100ticb.html