poj 3083 Children of the Candy Corn-白红宇

poj 3083 Children of the Candy Corn

阅读量：793 次

发布时间：2023-03-03

本文共 2256 字，大约阅读时间需要 7 分钟。

题目不难就是繁琐呀

代码如下：

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
#include 
        
          #include 
          #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; #define LL long long #define sint short int const int INF = 0x3f3f3f3f; priority_queue

, greater

> qt; const int N = 50; char graph[N][N]; typedef pair

point; queue

qt; int dist[N][N]; bool in[N][N]; int X[] = {-1, 0, 1, 0}; int Y[] = {0, 1, 0, -1}; int n, m; bool OK(int x, int y) { if (x >= 0 && x < n && y >= 0 && y < m && graph[x][y] != '#') return true; return false; } int spfa(int sx, int sy, int ex, int ey) { memset(in, false, sizeof(in)); memset(dist, -1, sizeof(dist)); qt.push(point(sx, sy)); in[sx][sy] = true; dist[sx][sy] = 1; while (!qt.empty()) { int x = qt.front().first; int y = qt.front().second; in[x][y] = false; qt.pop(); for (int i = 0; i < 4; ++i) { int l1 = x + X[i]; int l2 = y + Y[i]; if (OK(l1, l2) && (dist[l1][l2] == -1 || dist[l1][l2] > dist[x][y] + 1)) { dist[l1][l2] = dist[x][y] + 1; if (!in[l1][l2]) { in[l1][l2] = true; qt.push(point(l1, l2)); } } } } return dist[ex][ey]; } int Lsearch(int sx, int sy, int ex, int ey, int t) { int step = 1; int kx = sx, ky = sy; while (true) { if (kx == ex && ky == ey) break; bool flag = false; for (int i = (t + 3) % 4, j = 0; j < 4; ++j, i = (i + 4) % 4) { int l1 = kx + X[i]; int l2 = ky + Y[i]; if (OK(l1, l2)) { kx = l1; ky = l2; t = i; step++; flag = true; break; } } if (!flag) return INF; } return step; } int Rsearch(int sx, int sy, int ex, int ey, int t) { int step = 1; int kx = sx, ky = sy; while (true) { if (kx == ex && ky == ey) break; bool flag = false; for (int i = 0; i < 4; ++i) { int l1 = kx + X[(i + 3) % 4]; int l2 = ky + Y[(i + 3) % 4]; if (OK(l1, l2)) { kx = l1; ky = l2; t = i; step++; flag = true; break; } } if (!flag) return INF; } return step; }

这段代码实现了图形搜索算法，主要包括广度优先搜索（BFS）和深度优先搜索（DFS）的两种方法。代码中定义了一个常数N，用于表示网格的大小，graph数组用于表示网格中的墙体或通行区域。X和Y数组分别表示四个方向的移动向量。

代码的主要功能是从一个起点（sx, sy）开始，寻找从该点到目标点（ex, ey）的最短路径。Lsearch函数实现了另一种搜索算法，而Rsearch函数则是另一种方法。两种方法的区别主要在于搜索方向的选择顺序。

代码中还定义了OK函数，用于检查给定的位置是否在网格范围内并且不是墙体。spfa函数是广度优先搜索的标准实现，而Lsearch和Rsearch函数则是深度优先搜索的两种不同的实现方式。

整体来看，这段代码的编写风格比较直接，注重功能实现，但在代码优化和注释方面还有提升空间。代码的变量命名和注释都比较简洁，适合作为基础实现参考。

转载地址：http://bfxfk.baihongyu.com/

你可能感兴趣的文章