首页 > 其他分享 >kuangbin专题一 简单搜索 迷宫问题(POJ-3984)

kuangbin专题一 简单搜索 迷宫问题(POJ-3984)

时间:2023-04-15 20:47:44浏览次数:40  
标签:pair typedef int nx ny POJ kuangbin 3984 include

迷宫问题

Time Limit: 1000MS Memory Limit: 65536K

Description

定义一个二维数组:

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径,格式如样例所示。

Sample Input

5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4


解题思路

这个题其实有点搞笑,POJ上居然只有一组数据,水题中的水题......我后来用的是Acwing上的测评系统,还是很正常的hhh。

这道题是经典的BFS求最短路模型,但是需要我们去输出具体的路径,这是比较考验逆向思维的地方。要求出从左上角到右下角的最短路的具体方案,以正向思维来考虑是不太行的,从走出的第一步开始,你便不知道到底走到哪个方向会求得未来的最优解。所以,我们需要采取一种逆向思维,即以所要到达的终点为起点进行BFS。在BFS过程中,每个点第一次访问一定是距离最短的,所以由此可以求出所有点的前驱,直到到达左上角。然后从左上角这个点开始反向输出所有记录的前驱,就可以得到最优且合法的到达右下角的具体路径。

/*   一切都是命运石之门的选择  El Psy Kongroo  */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, pii> psi;
typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;

const int N = 1010;
bool vis[N][N];
int g[N][N];
pii pre[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n;

void bfs(){
    queue<pii> q;
    q.push(make_pair(n - 1, n - 1));
    vis[n - 1][n - 1] = true;
    
    while(!q.empty()){
        pii p = q.front();
        int x = p.first, y = p.second;
        q.pop();
        
        for(int k = 0; k < 4; k ++ ){
            int nx = x + dx[k], ny = y + dy[k];
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(g[nx][ny] || vis[nx][ny]) continue;
        
            q.push(make_pair(nx, ny));
            vis[nx][ny] = true;
            pre[nx][ny] = p;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++ )
            cin >> g[i][j];
    
    bfs();
    
    //输出反向bfs的前驱,即正向的路径
    pii end = make_pair(0, 0);
    while(end.first != n - 1 || end.second != n - 1){
        int x = end.first, y = end.second;
        cout << x << ' ' << y << endl;
        end = pre[x][y];
    }
    cout << n - 1 << ' ' << n - 1;
    
    return 0;
}

标签:pair,typedef,int,nx,ny,POJ,kuangbin,3984,include
From: https://www.cnblogs.com/MAKISE004/p/17321795.html

相关文章

  • kuangbin专题一 简单搜索 石油储备(HDU-1241)
    OilDepositsTimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)ProblemDescriptionTheGeoSurvCompgeologicsurveycompanyisresponsiblefordetectingundergroundoildeposits.GeoSurvCompworkswithonelargerectangula......
  • kuangbin专题一 简单搜索 起火迷宫(UVA-11624)
    Fire!DescriptionJoeworksinamaze.Unfortunately,portionsofthemazehavecaughtonfire,andtheownerofthemazeneglectedtocreateafireescapeplan.HelpJoeescapethemaze.GivenJoe’slocationinthemazeandwhichsquaresofthemazeareo......
  • kuangbin专题一 简单搜索 点火游戏(FZU-2150)
    FireGameDescriptionFatbrotherandMazeareplayingakindofspecial(hentai)gameonanN*Mboard(Nrows,Mcolumns).Atthebeginning,eachgridofthisboardisconsistingofgrassorjustemptyandthentheystarttofireallthegrass.Firstlyt......
  • kuangbin专题一 简单搜索 罐子(POJ-3414)
    PotsTimeLimit:1000MS MemoryLimit:65536KDescriptionYouaregiventwopots,havingthevolumeofAandBlitersrespectively.Thefollowingoperationscanbeperformed:FILL(i)fillthepoti(1≤i≤2)fromthetap;DROP(i)emptythep......
  • poj2750(线段树+复杂区间合并)
    PottedFlowerPOJ-2750思路:我们将题目简单化,假设我们要求的是序列的最大连续子段和,且可以包括所有数。我们的线段树需要维护这段区间的最大前缀和pre,最大后缀和suf,区间和sum,区间连续最大和mx。那么难点就在于如何由子节点更新父节点。我们可以知道,tr[p].sum=tr[lc].sum......
  • kuangbin专题一 简单搜索 找倍数(POJ-1426)
    FindTheMultipleTimeLimit:1000MS MemoryLimit:10000KDescriptionGivenapositiveintegern,writeaprogramtofindoutanonzeromultiplemofnwhosedecimalrepresentationcontainsonlythedigits0and1.Youmayassumethatnisnotgreaterth......
  • poj2777(线段树)
    CountColorPOJ-2777思路:暴力能过,线段树维护这个区间的颜色,如果是混色则置为1,如果是单一颜色则设为这个颜色,修改就是正常的区间修改,区间查询就要变一下。还有题解是用二进制做得,可以学一下。#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<fstream>#inc......
  • kuangbin专题一 简单搜索 翻转(POJ-3279)
    FliptileTimeLimit:2000MS MemoryLimit:65536KDescriptionFarmerJohnknowsthatanintellectuallysatisfiedcowisahappycowwhowillgivemoremilk.HehasarrangedabrainyactivityforcowsinwhichtheymanipulateanM×Ngrid(1≤M≤15;1≤......
  • poj 2182
    LostCowsPOJ-2182与这题一样BuyTickets-POJ2828-VirtualJudge(csgrandeur.cn)题意:有1~NN个数字,这N个数字的顺序是打乱的,从第二个数字开始给你它的前面有多少个数字比他小思路:输入的数字都要加一,然后我们从后往前遍历,在线段树中如果左子树的sum‘>sum,则进入左子......
  • kuangbin专题一 简单搜索 抓住那头牛(POJ-3278)
    CatchThatCowTimeLimit:2000MS MemoryLimit:65536KTotalSubmissions:210291 Accepted:63838DescriptionFarmerJohnhasbeeninformedofthelocationofafugitivecowandwantstocatchherimmediately.HestartsatapointN(0≤N≤100,000)on......