2021秋季《数据结构》_EOJ 1025. 迷宫

题目

思路

dfs bfs复习

代码

dfs

// dfs
#include<bits/stdc++.h>
using namespace std;int a[101][101] = {
    {
    0}};int n, startx, starty, endx, endy;
int flag = 0;void dfs(int x, int y)
{
    // cout<<"x,y="<<x<<' '<<y<<endl;if(x<0||x>=n||y<0||y>=n){
    return;}if(x==endx && y==endy){
    flag = 1;// cout<<"*"<<endl;return;}if(a[x][y]==1)  // 有障碍物{
    return;}a[x][y]=1;  // 不能走回头路，否则会陷入死循环dfs(x+1, y+1);dfs(x+1, y);dfs(x+1, y-1);dfs(x, y+1);dfs(x, y-1);dfs(x-1, y+1);dfs(x-1, y);dfs(x-1, y-1);return;
}int main()
{
    cin>>n;cin>>startx>>starty>>endx>>endy;for(int i = 0; i < n; i++){
    string s; cin>>s;for(int j = 0; j < n; j++)a[i][j] = s[j]-'0';}// for(int i = 1; i <= n; i++)// {
    // for(int j = 1; j <= n; j++)// cout<<a[i][j];// cout<<endl;// }dfs(startx, starty);if(flag==1) cout<<"yes"<<endl;else cout<<"no"<<endl;system("pause");return 0;
}

记得地图数组中实时将走过的路赋为1，避免进入死循环

bfs

#include<bits/stdc++.h>
using namespace std;typedef struct point
{
    int x, y;
}Point;Point q[10001];
int a[101][101] = {
    {
    0}};
int book[101][101] = {
    {
    0}};  // 标记是否被走过 int dir[8][2] = {
    {
    1,1},{
    1,0},{
    1,-1},{
    0,1},{
    0,-1},{
    -1,1},{
    -1,0},{
    -1,-1}
};int main()
{
    int n; cin>>n;int startx, starty, endx, endy;cin>>startx>>starty>>endx>>endy;for(int i = 0; i < n; i++){
    string s; cin>>s;for(int j = 0; j < n; j++)a[i][j] = s[j]-'0';}int front = 1, rear = 1;q[rear].x = startx;q[rear].y = starty;book[startx][starty] = 1;rear++;while (front<rear)  // 队不空{
    for(int i = 0; i < 8; i++)  // 遍历八个方向{
    int tx = q[front].x+dir[i][0];int ty = q[front].y+dir[i][1];if(tx<0 || tx>=n || ty<0 || ty>=n || a[tx][ty]==1)// 有障碍物或者超出地图continue;if(a[tx][ty]==0 && book[tx][ty]==0)  // 可通行且没走过{
    book[tx][ty]=1;  // 标记走过q[rear].x = tx;q[rear].y = ty;rear++;  // 该点入队}}front++;}if(book[endx][endy]==1) cout<<"yes"<<endl;else cout<<"no"<<endl;system("pause");return 0;}