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

在这个问题中，我们需要判断天灾军团是否可以通过现有的通道从n号隘口到达1号隘口，如果可以，我们还需要找出最少需要经过的通道数量。

方法思路

这个问题可以看作是一个图的最短路径问题。具体来说，我们有一个有向图，其中节点表示隘口，边表示通道。我们需要找到从n号隘口到1号隘口的最短路径。如果不存在这样的路径，则输出“NO”。

为了解决这个问题，我们可以使用广度优先搜索（BFS），因为BFS能够在图中找到最短路径。我们从n号隘口开始，逐层搜索，直到到达1号隘口或所有可能的节点都已访问。每次访问一个新节点时，我们记录经过的通道数量，当找到目标节点时返回通道数量。

解决代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct Node {    int data;    int step;    Node(int d, int s) : data(d), step(s) {}};bool BFS(Node start) {    queue
      
        q;    bool visited[1005] = {false};    q.push(start);    visited[start.data] = true;        while (!q.empty()) {        Node current = q.front();        q.pop();                if (current.data == 1) {            return true;        }                for (int i = 1; i <= n; ++i) {            if (!visited[i] && current.step + 1 <= start.step + n) {                if (Map[current.data][i]) {                    visited[i] = true;                    Node next(i, current.step + 1);                    q.push(next);                }            }        }    }    return false;}int main() {    ios::sync_with_stdio(false);    int n, m;        while (true) {        cin >> n >> m;        if (m == 0) {            break;        }        int a, b;        vector
       
        
         > edges; for (int i = 0; i < m; ++i) { edges.push_back(make_pair(a, b)); } Map[n+1][1] = true; if (BFS(Node(n, 0))) { cout << (current.step + 1) << endl; } else { cout << "NO" << endl; } }}
        
       
      
     
    
   

代码解释

这个方法确保了在给定的约束条件下，高效地解决问题，并且能够处理大规模输入。

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