山东省建设监理网站,电商网站建设维护费会计分录,东莞网站建设什么价格便宜,免费数据库网站空间题目传送门 题意#xff1a;从r走到a#xff0c;遇到x多走一步#xff0c;问最小走到a的步数 分析#xff1a;因为r有多个#xff0c;反过来想从a走到某个r的最小步数#xff0c;简单的BFS。我对这题有特殊的感情#xff0c;去年刚来集训队时肉鸽推荐了这题#xff0c;… 题目传送门 题意从r走到a遇到x多走一步问最小走到a的步数 分析因为r有多个反过来想从a走到某个r的最小步数简单的BFS。我对这题有特殊的感情去年刚来集训队时肉鸽推荐了这题当时什么都不会看个数组模拟队列的BFS看的头晕现在看起来也不过如此额当年开始是从r走到a的因为数据巨弱才过的应该要用到优先队列。 /************************************************
* Author :Running_Time
* Created Time :2015/9/25 星期五 09:13:51
* File Name :B_BFS.cpp************************************************/#include cstdio
#include algorithm
#include iostream
#include sstream
#include cstring
#include cmath
#include string
#include vector
#include queue
#include deque
#include stack
#include list
#include map
#include set
#include bitset
#include cstdlib
#include ctime
using namespace std;#define lson l, mid, rt 1
#define rson mid 1, r, rt 1 | 1
typedef long long ll;
const int N 2e2 10;
const int INF 0x3f3f3f3f;
const int MOD 1e9 7;
const double EPS 1e-8;
struct Angle {int x, y, step;Angle () {}Angle (int x, int y, int step) : x (x), y (y), step (step) {}
};
int dx[4] {-1, 1, 0, 0};
int dy[4] {0, 0, -1, 1};
bool vis[N][N];
char maze[N][N];
int n, m;bool judge(int x, int y) {if (x 1 || x n || y 1 || y m || vis[x][y] || maze[x][y] #) return false;else return true;
}void BFS(Angle s) {int ret INF;memset (vis, false, sizeof (vis));queueAngle Q; Q.push (s);vis[s.x][s.y] true;while (!Q.empty ()) {Angle r Q.front (); Q.pop ();for (int i0; i4; i) {int tx r.x dx[i];int ty r.y dy[i];if (!judge (tx, ty)) continue;vis[tx][ty] true;if (maze[tx][ty] r) {ret min (ret, r.step 1); continue;}else if (maze[tx][ty] x) {Q.push (Angle (tx, ty, r.step 2)); continue;}else Q.push (Angle (tx, ty, r.step 1));}}if (ret INF) puts (Poor ANGEL has to stay in the prison all his life.);else printf (%d\n, ret);
}int main(void) {while (scanf (%d%d, n, m) 2) {for (int i1; in; i) {scanf (%s, maze[i] 1);}bool find false; Angle start;for (int i1; in !find; i) {for (int j1; jm; j) {if (maze[i][j] a) {start Angle (i, j, 0);find true; break;}}}BFS (start);}return 0;
}当年的代码不忍直视。。。 #includestdio.h
typedef struct point
{int x,y,step;
}target;
int N,M,dir[4][2]{0,1,0,-1,1,0,-1,0},ax,ay;
int flag[202][202];
char map[302][302];
target que[40005];
int BFS(target start)
{int end,top,i;int min1000000;target in,next;endtop0;que[top]start;while (topend){inque[end];end(end1);for (i0;i4;i){next.xin.xdir[i][0];next.yin.ydir[i][1];if (map[next.x][next.y]r){if (minin.step1)minin.step1;}if (next.x0next.xNnext.y0next.yMmap[next.x][next.y]!#){if (flag[next.x][next.y]in.step1){next.stepin.step1;if (map[next.x][next.y]x)next.step;flag[next.x][next.y]next.step;top(top1);que[top]next;}}}}if (min!1000000)return min;elsereturn -1;
}
int main()
{int i,j,num;target start;while (scanf(%d%d,N,M)!EOF){for (i0;iN;i){scanf(%s,map[i]);for (j0;jM;j){flag[i][j]1000000;if (map[i][j]a){//map[i][j].;axi;ayj;}}}start.xax;start.yay;start.step0;//map[ax][ay].;numBFS(start);if (num-1)printf(Poor ANGEL has to stay in the prison all his life.\n);elseprintf(%d\n,num);}return 0;
}转载于:https://www.cnblogs.com/Running-Time/p/4837255.html
