贺州学院ivy


私信TA

用户名:Livy

访问量:536

签 名:

好好学习,天天向上,汝何秀?

排  名 22
经  验 5221
参赛次数 4
文章发表 25
年  龄 0
在职情况
学  校 贺州学院
专  业 软件工程

  自我简介:

假猪套天下第一

解题思路:

利用广搜算法来做这题,一般像这种二维数组的地图,让你走去一个地方,求最短路程都可以用深搜或者广搜,不过地图一旦大了,那么深搜就较为容易超时的,看情况来吧,地图小,深搜和广搜都可以,地图大了,还是建议广搜好一点


注意事项:


广搜的特点就是,记录起点坐标,以起点为head,遍历上下左右四个方向的地点,符合条件的地点则存储,然后tail++,不符合就不存储进来。遍历4个方向后,head++,以新的head为起点,再次遍历四个方向,符合的tail++,不符合的就下一个方向遍历,直至4个方向都尝试过了。然后又是head++.......,如此反复的一个过程





如:

3
A  +  -
+  -  +
+  -  B

可以看出答案是4对吧,A-----》(1,2)-----》(2,2)-----》(2,3)-----》B   一共四步
或者              A-----》(1,2)-----》(1,3)-----》(2,3)-----》B   一共四步

我就选第一个来说吧
一开始,在输入过程中就记录下A的坐标位置了,然后从A的四个方向遍历,符合条件就存储,tail++,不符合就不存储

h表示head,t表示tail,第四行数字表示步数

n数组xiabi下标1-m*m
第一次遍历,head(A)的位置(1,1),因为符合的只有(1,2)和(2,1)
h           t
1   2   3   4   5   6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21
A   12  21
0   1   1

第二次遍历,head的位置(1,2),因为符合的只有(1,3)和(2,2)
    h               t
1   2   3   4   5   6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21
A   12  21  31  22
0   1   1   2   2

第三次遍历,head的位置(2,1)没有符合条件的
        h           t
1   2   3   4   5   6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21
A   12  21  31  22
0   1   1   2   2

第四次遍历,head的位置(3,1),因为符合的只有(2,3)           
            h          t
1   2   3   4   5   6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21
A   12  21  31  22  23
0   1   1   2   2   3


.........下面的步骤我就不写了,慢慢理解一下






参考代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string.h>
#include<math.h>
#include<string>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<iomanip>
using namespace std;
//地图
char mmap[150][150];
//标技数组,就走过的地点就不再重复走了
bool book[150][150];
//方向数组,控制方向,我的顺序是右下左上
int nnext[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
//判断走不到终点的时候,就输出-1的标志变量,ff=false则说明可以走到B,ff=true则走不到B
bool ff = false;
//广搜用来存放每一步可以走的结构体数组,包含坐标,步数,和字符符号,因为+-才能走,++和--都不行,是用来存储字符比较下一步可不可以走的
typedef struct node{
 int x, y, step;
 char flag;
}node;
node n[10200];//广搜数组一般大小为m*m,因为最大是100,也就是100*100=10000,我开大一点

int main(){
 //m*m地图
 int m;
 cin >> m;
 getchar();//输入m后,吃掉回车
 int head, tail,x,y,tx,ty;
 for (int i = 1; i <= m; i++){
  for (int j = 1; j <= m; j++){
   scanf("%c", &mmap[i][j]);
   if (mmap[i][j] == 'A'){//记录起点位置,记下坐标
    x = i, y = j;
   }
   getchar();//吃掉空格和换行的回车
  }
 }
 //初始化
 head = tail = 1;//广搜实质上可以理解成一个队列,头和尾
 n[tail].x = x; n[tail].y = y; n[tail].step = 0; n[tail].flag = ' ';
 book[x][y] = 1;//标记起点位置A,说明待会广搜的话就不会再走回来起点A的位置
 tail++;
 //广搜的核心
 while (head < tail){
  for (int i = 0; i < 4; i++){
   tx = n[head].x + nnext[i][0];
   ty = n[head].y + nnext[i][1];
   //边界,超过地图边界,就不会走
   if (tx > m || tx < 1)continue;
      if(ty > m || ty < 1)continue;
   //没去过的地点,而且符合一正一负
   if (book[tx][ty] == 0 && n[head].flag != mmap[tx][ty]){
    book[tx][ty] = 1;
    n[tail].y = ty;
    n[tail].x = tx;
    n[tail].step = n[head].step+1;//步数等于上一步的步数+1
    n[tail].flag = mmap[tx][ty];
    tail++;
   }
  }
  if (n[head].flag == 'B'){
   cout << n[head].step;
   ff = true;
   break;
  }
  head++;
 }
 if (!ff)cout << -1;
 system("pause");
 return 0;
}



  评论区

写的不错,期待有深搜的题解~
2018-09-17 10:24:09 | |
  • «
  • 1
  • »