poj2312

poj2312

priority_queue的bfs

priority_queue的bfs相当于使用了dijkstra的思想。

poj2312
poj2312
View Code

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <queue> using namespace std; #define maxn 305 struct Point { int x, y, w; }s, t; int n, m; char map[maxn][maxn]; bool vis[maxn][maxn]; int dir[4][2] = { { 1,0},{-1,0},{ 0,1},{ 0,-1}}; bool operator < (const Point &a, const Point &b) { return a.w > b.w; } void input() { for (int i = 0; i < n; i++) scanf("%s", map[i]); } void work() { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (map[i][j] == 'Y') { s.x = i; s.y = j; s.w = 0; map[i][j] = 'E'; } if (map[i][j] == 'T') { t.x = i; t.y = j; map[i][j] = 'E'; } } } bool ok(Point a, int &step) { if (a.x < 0 || a.y < 0 || a.x >= n || a.y >= m) return false; if (vis[a.x][a.y]) return false; if (map[a.x][a.y] == 'S' ||map[a.x][a.y] == 'R') return false; if (map[a.x][a.y] == 'E') { step = 1; return true; } step = 2; return true; } int bfs() { priority_queue <Point> pq; memset(vis, 0, sizeof(vis)); pq.push(s); vis[s.x][s.y] = true; while (!pq.empty()) { Point u = pq.top(); pq.pop(); if (u.x == t.x && u.y == t.y) return u.w; Point v; for (int i = 0; i < 4; i++) { v.x = u.x + dir[i][0]; v.y = u.y + dir[i][1]; int step; if (ok(v, step)) { v.w = u.w + step; pq.push(v); vis[v.x][v.y] = true; } } } return -1; } int main() { //freopen("t.txt", "r", stdin); while (scanf("%d%d", &n, &m), n | m) { input(); work(); printf("%d\n", bfs()); } return 0; }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/110368.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • sha1给出了三种新的sha版本_sha1怎么下载

    sha1给出了三种新的sha版本_sha1怎么下载注:如果出现【’keytool’不是内部或外部命令,也不是可运行的程序或批处理文件。】请参照下面的链接https://blog.csdn.net/csdnhejingzhou/article/details/50643246开发版SHA11.在AndroidStudio最下面找到Terminal点击2.切换到C盘,cd到Users\Administrator\.android…

  • LINUX centos 安装图形界面

    LINUX centos 安装图形界面以Centos6.5为例演示一下如何安装桌面环境。一、首先查看系统的运行级别以及是否安装了桌面环境1、使用命令runlevel查看当前系统运行级别,如图所示2、使用命令yumgrouplist|more查看是否安装了桌面环境的组件,如图所示二、再次从上面分析的结果看到,当前运行级别是3,而且也没有安装桌面环境的软件。然后我们使用命令查看一下桌…

  • Latex 公式在线可视化编辑器

    Latex 公式在线可视化编辑器本文介绍定制latex公式在线编辑器

  • PDB 文件

    PDB 文件PDB文件什么是PDB文件PDB(ProgramDataBase)即程序的基本数据,是VS编译链接时生成的文件,每个程序集(EXE或DLL)都有一个与之对应的PDB文件。DPB文件主要存储了VS调试程序时所需要的基本信息,主要包括源文件名、变量名、函数名、对应的行号等等。因为存储的是调试信息,所以一般情况下PDB文件是在Debug模式下才会生成。…

  • mysql 同步远程数据库_两个sql数据库数据实时同步

    mysql 同步远程数据库_两个sql数据库数据实时同步1.服务配置说明:服务器名称服务器地址数据库名称用户名密码端口数据库服务器A121.xx.xx.xxyoujihui_zsrootyoujihui3306数据库服务器B120.yy.yy.yyy

    2022年10月15日
  • spidermonkeys_嵌入式开发网站

    spidermonkeys_嵌入式开发网站
    利用SpiderMonkey进行嵌入式开发——学习总结
    关键词:SpiderMonkey                                          利用SpiderMonkey进行嵌入式开发——学习总结许峰2007/07/30最近在学习javascript引擎SpiderMonkey,学了一个星期了,终于有点眉目,现将学习经验记录下来,已被后用。
    一下将逐步记录我学习的过程。1、下载源文件以及编译
    在 http://ftp.mozilla

    2022年10月16日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号