NEUQ-ACM预备队训练-week4(搜索)

1.P1605 迷宫

戳这里跳到原题

题目描述

给定一个 N×M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 N,M,T 分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 SX,SY,FX,FY，SX,SY 代表起点坐标，FX,FY 代表终点坐标。

接下来 T 行，每行两个正整数，表示障碍点的坐标。

输出格式

输出从起点坐标到终点坐标的方案总数。

输入输出样例

输入

2 2 1
1 1 2 2
1 2

输出

1

说明/提示

对于 100% 的数据，1≤N,M≤5，1≤T≤10，1≤SX,FX≤N，1≤SY,FY≤M。

从迷宫入口找到出口很明显是要用深搜来做，而且人家要求输出解的个数，所以就每次搜索以后就给他回溯一下，一直找直到碰到出口就结束，顺便把解的个数 ，具体的做法我都在代码里面写成注释了，最后输出这个解的个数就AC了

1.  
   #include <iostream>
2.  
   using namespace std;
3.  
   int sum = 0;
4.  
   int x, y, mnt, sx, sy, fx, fy, arr[7][7] = {0};
5.  
    
6.  
   void DFS(int x,int y) {
7.  
   arr[x][y] = 2;//标记这个点表示走过
8.  
   if(x == fx&&y == fy){//遇到出口就sum 并且return回去
9.  
   sum ;
10.  
    return;
11.  
    }
12.  
    // if(arr[x-1][y]==0){//如果没走过并且没有障碍
13.  
    // DFS(x-1,y);//继续深搜
14.  
    // arr[x-1][y] = 0;//回溯
15.  
    // }//下面都是一样的不过合成到一行了
16.  
    if(arr[x-1][y]==0){DFS(x-1,y);arr[x-1][y] = 0;}
17.  
    if(arr[x 1][y]==0){DFS(x 1,y);arr[x 1][y] = 0;}
18.  
    if(arr[x][y 1]==0){DFS(x,y 1);arr[x][y 1] = 0;}
19.  
    if(arr[x][y-1]==0){DFS(x,y-1);arr[x][y-1] = 0;}
20.  
    }
21.  
     
22.  
     
23.  
    int main() {
24.  
    //一堆输入
25.  
    cin >> x >> y >> mnt;
26.  
    cin >> sx >> sy >> fx >> fy;
27.  
    //地图的初始化
28.  
    for (int i = 0; i <= x 1; i ) {
29.  
    for (int j = 0; j <= y 1; j ) {
30.  
    if (i == 0 || i == x 1 || j == 0 || j == y 1 )
31.  
    arr[i][j] = 1;//墙都设成1
32.  
    }
33.  
    }
34.  
    int tempx, tempy;
35.  
    for (int i = 0; i < mnt; i ) {
36.  
    cin >> tempx >> tempy;
37.  
    arr[tempx][tempy] = 1;//障碍和墙一样看待，都不能走，设成1
38.  
    }
39.  
     
40.  
    // for (int i = 0; i <= x 1; i ) {
41.  
    // for (int j = 0; j <= y 1; j ) {
42.  
    // cout << arr[i][j] << ' ';
43.  
    // }
44.  
    // cout << endl;
45.  
    // }//输出地图检测输入是否正确
46.  
    //开搜
47.  
    DFS(sx,sy);
48.  
    cout << sum;
49.  
    return 0;
50.  
    }

2.P1443 马的遍历

原题位置

题目描述

有一个 n×m 的棋盘，在某个点 (x, y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 n, m, x, y。

输出格式

一个 n×m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1）。

输入输出样例

输入

3 3 1 1

输出

0    3    2    
3    -1   1    
2    1    4    

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤x≤n≤400，1≤y≤m≤400。

这个题一眼广搜，就是把遍历到的节点的下一步能走的节点给他放到队列里面，然后把这个节点赋值，再走到下一个节点，一层一层的搜索，直到队列里面没有新成员了，走不下去了，就可以退出了，直接把这个矩阵输出就OK，还是具体操作写在注释里，代码贴上

1.  
   #include <iostream>
2.  
   #include <cstring>
3.  
   using namespace std;
4.  
   #define MAXX 405
5.  
   #define MAXY 405
6.  
   #define DUILIE 164025
7.  
    
8.  
   int main()
9.  
   {
10.  
    //准备工作
11.  
    char arr[MAXX][MAXY];
12.  
    memset(arr,-1,MAXX*MAXY);//把这个矩阵初始化成-1表示没有走过
13.  
    int b[2][DUILIE];//用一个二维数组当队列了，第一行存x值，第二行存y值
14.  
    int dx[8]={-1,-2,-2,-1,1,2,2,1};
15.  
    int dy[8]={2,1,-1,-2,2,1,-1,-2};//把八个方向用数组存一下，后面直接遍历这个数组就OK
16.  
    int start = 0,end = 0;//用给队列的两个变量，存队列的头尾
17.  
    int n,m,x,y,step=0;//矩阵大小和初始位置都在这里，step是步数
18.  
     
19.  
    //开始输入
20.  
    cin >> n >> m >> x >> y ;
21.  
    arr[x][y] = 0;//起始位置设成0
22.  
    b[0][end] = x;
23.  
    b[1][end ] = y;//把起始位置压入队列
24.  
     
25.  
    //广搜开始
26.  
    while(start!=end){//只要队列里还有元素
27.  
    int temp = end;
28.  
    for(;start!=temp;start = (start 1)%DUILIE){
29.  
    //把相邻的位置压入队列
30.  
    for(int i=0;i<8;i )
31.  
    {
32.  
    int nx=b[0][start] dx[i],ny=b[1][start] dy[i];
33.  
    if(nx>0&&nx<=n&&ny>0&&ny<=m&&arr[nx][ny]==-1){
34.  
    b[0][end] = nx;
35.  
    b[1][end] = ny;
36.  
    end = (end 1)%DUILIE;
37.  
    arr[nx][ny] = -2;//一定要设成跟-1不一样的区分一下，不然有可能多次压入
38.  
    }
39.  
    }
40.  
    arr[b[0][start]][b[1][start]] = step;//赋值
41.  
    }
42.  
    step ;//步数
43.  
    }
44.  
     
45.  
    //简单输出
46.  
    for(int i = 1;i <= n;i ){
47.  
    for(int j = 1;j <= m;j ){
48.  
    printf("%-5d",arr[i][j]);
49.  
    }cout << endl;
50.  
    }
51.  
     
52.  
    return 0;
53.  
    }

这篇好文章是转载于：学新通技术网