?

題目傳送門

題意：從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));queue<Angle> Q; Q.push (s);vis[s.x][s.y] = true;while (!Q.empty ()) {Angle r = Q.front (); Q.pop ();for (int i=0; i<4; ++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 i=1; i<=n; ++i) {scanf ("%s", maze[i] + 1);}bool find = false; Angle start;for (int i=1; i<=n && !find; ++i) {for (int j=1; j<=m; ++j) {if (maze[i][j] == 'a') {start = Angle (i, j, 0);find = true; break;}}}BFS (start);}return 0; }

?

當年的代碼不忍直視。。。

#include<stdio.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 min=1000000;target in,next;end=top=0;que[top]=start;while (top>=end){in=que[end];end=(end+1);for (i=0;i<4;i++){next.x=in.x+dir[i][0];next.y=in.y+dir[i][1];if (map[next.x][next.y]=='r'){if (min>in.step+1)min=in.step+1;}if (next.x>=0&&next.x<N&&next.y>=0&&next.y<M&&map[next.x][next.y]!='#'){if (flag[next.x][next.y]>in.step+1){next.step=in.step+1;if (map[next.x][next.y]=='x')next.step++;flag[next.x][next.y]=next.step;top=(top+1);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 (i=0;i<N;i++){scanf("%s",map[i]);for (j=0;j<M;j++){flag[i][j]=1000000;if (map[i][j]=='a'){//map[i][j]='.';ax=i;ay=j;}}}start.x=ax;start.y=ay;start.step=0;//map[ax][ay]='.';num=BFS(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

總結

以上是生活随笔為你收集整理的BFS HDOJ 1242 Rescue的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。