【杭电oj1242】Rescue

梦里梦外; 2022-09-24 11:24 220阅读 0赞

![这里写图片描述][20160729230431627]  
![这里写图片描述][20160729230445951]

在下是菜鸡，一个细节没注意到，非void函数是要有返回值的，可是我就一直没加那个return -1；一直哇，桑心。希望以后我能避免犯这种错误。  
DFS代码我也会贴上的，很快。

BFS+优先队列：

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<queue>
    using namespace std;
    const int N = 210;
    char c[N][N];
    bool vis[N][N];
    int n,m,x,y,ex,ey;
    int px[4]= {
       1,-1,0,0};
    int py[4]= {
       0,0,-1,1};
    struct node {
        int tx,ty;
        int time;
        bool friend operator<(node A,node B) {
            return A.time>B.time;
        }
    } s;
    int dfs(int u,int v) {
        s.tx=u,s.ty=v,s.time=0;
        priority_queue<node>Q;
        Q.push(s);
        vis[u][v]=1;
        while(!Q.empty()) {
            node now;
            now=Q.top();
            Q.pop();
            if(now.tx==ex&&now.ty==ey) {
                return now.time;
            }
            for(int l=0; l<4; l++) {
                node end;
                end.tx=now.tx+px[l];
                end.ty=now.ty+py[l];
                end.time=now.time;
                if(c[end.tx][end.ty]!='#'&&!vis[end.tx][end.ty]&&end.tx>=0&&end.ty>=0&&end.tx<n&&end.ty<m) {
        
                    if(c[end.tx][end.ty]=='x')
                        end.time+=2;
                    else
                        end.time++;
                    vis[end.tx][end.ty]=1;
                    Q.push(end);
                }
            }
        }
        return -1;
    }
    int main() {
        while(scanf("%d%d",&n,&m)!=EOF) {
            memset(vis,false,sizeof(vis));
            for(int l=0; l<n; l++) {
                scanf("%s",c[l]);
            }
            for(int i=0; i<n; i++)
                for(int j=0; j<m; j++) {
                    if(c[i][j]=='r')
                        x=i,y=j;
                    if(c[i][j]=='a')
                        ex=i,ey=j;
                }
            int ans=dfs(x,y);
            if(ans==-1)
                printf("Poor ANGEL has to stay in the prison all his life.\n");
            else
                printf("%d\n",ans);
        }
        return 0;
    }

[http://acm.hdu.edu.cn/showproblem.php?pid=1242][http_acm.hdu.edu.cn_showproblem.php_pid_1242]

[20160729230431627]: /images/20220719/6d6c76bbf0f94ee1a87114b64709838f.png
[20160729230445951]: /images/20220719/f0409a42c48e4a969f7ce7457fa1a6ff.png
[http_acm.hdu.edu.cn_showproblem.php_pid_1242]: http://acm.hdu.edu.cn/showproblem.php?pid=1242