深搜怎么写

深度优先搜索 (DFS) 是一种常用的图遍历算法，其基本思想是从图的某个顶点出发，沿着一条路一直走到底，直到该路走到不能走为止，然后返回到上一个顶点，从另一条路继续走到底，直到所有的顶点都被访问过为止。下面是深搜的一种常见写法：

visited = set()  # 记录已经访问过的节点

def dfs(node):
    if node in visited:
        return
    visited.add(node)
    # 处理当前节点
    for neighbor in node.neighbors:
        dfs(neighbor)  # 递归访问未访问过的邻居节点

其中，`visited` 集合用于记录已经访问过的节点，避免重复访问。`dfs` 函数的参数是当前节点，首先将其加入到 `visited` 集合中，然后处理当前节点。接着，遍历当前节点的所有邻居节点，如果某个邻居节点还没有被访问过，则递归调用 `dfs` 函数访问该节点。这样就可以实现深度优先搜索了。

相关问题

用python写一个深搜

可以使用以下代码实现深度优先搜索：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

其中，graph表示图的邻接表，start表示起始节点，visited表示已经访问过的节点集合。函数会递归地访问与start相邻的未访问过的节点，直到所有节点都被访问过为止。

按下列思路写个qt c++消消乐代码：1.获取玩家输入(游戏地图边框大小: n)，作不合法处理;2.初始化:随机生成地图界面；do{3.输出当前地图界面，4.获取玩家鼠标左键点击位置(位于控制台窗口内)，作不合法处理，5.深搜(dfs)，搜索四连通(四个方向连通且同色)块，6.统计此次消除的得分，7.随机生成数(代表颜色)填补上次消除空白处，}while(地图界面未形成无法消除情况);总体形成玩家消除，机器填补的循环过程

以下是按照你提供的思路写的Qt C++消消乐代码示例：

#include <QtWidgets>

// 定义游戏地图大小的常量
const int kMapSize = 10;

class XxGame : public QWidget {
  Q_OBJECT

public:
  XxGame(QWidget* parent = nullptr) : QWidget(parent) {
    // 获取玩家输入
    bool ok;
    int n = QInputDialog::getInt(this, "XxGame", "请输入游戏地图边框大小:", 10, 1, 100, 1, &ok);
    if (!ok) {
      // 玩家取消输入，直接退出游戏
      qApp->quit();
      return;
    }
    if (n <= 0) {
      // 游戏地图大小不合法，提示玩家并退出游戏
      QMessageBox::warning(this, "XxGame", "游戏地图边框大小不合法!");
      qApp->quit();
      return;
    }

    // 初始化游戏地图
    map_.resize(n);
    for (int i = 0; i < n; ++i) {
      map_[i].resize(n);
      for (int j = 0; j < n; ++j) {
        // 随机生成地图格子的颜色
        map_[i][j] = qrand() % 5;
      }
    }

    // 设置游戏窗口大小
    setFixedSize(n * 50, n * 50);

    // 显示游戏地图
    update();

    // 进入游戏主循环
    QTimer::singleShot(0, this, &XxGame::gameLoop);
  }

protected:
  void paintEvent(QPaintEvent*) override {
    QPainter painter(this);
    int n = map_.size();
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        // 绘制地图格子
        QRect rect(j * 50, i * 50, 50, 50);
        painter.fillRect(rect, colors_[map_[i][j]]);
        painter.drawRect(rect);
      }
    }
  }

  void mousePressEvent(QMouseEvent* event) override {
    if (event->button() == Qt::LeftButton) {
      // 获取玩家鼠标左键点击位置
      int x = event->x() / 50;
      int y = event->y() / 50;
      int n = map_.size();
      if (x >= 0 && x < n && y >= 0 && y < n) {
        // 点击位置合法，进行搜索和消除操作
        bool ok = searchAndRemove(x, y);
        if (ok) {
          // 统计得分
          score_ += 10;
          // 填补空白处
          fillBlank();
          // 输出当前得分和地图界面
          qDebug() << "Score:" << score_;
          qDebug() << map_;
          // 更新游戏界面
          update();
        }
      }
    }
  }

private:
  bool searchAndRemove(int x, int y) {
    // 深搜搜索四连通块
    int color = map_[x][y];
    QVector<QPoint> to_remove;
    QVector<QPoint> visited;
    dfs(x, y, color, to_remove, visited);

    if (to_remove.size() >= 2) {
      // 找到了可消除块，进行消除操作
      for (const auto& p : to_remove) {
        map_[p.x()][p.y()] = -1;
      }
      return true;
    } else {
      // 没有可消除块
      return false;
    }
  }

  void dfs(int x, int y, int color, QVector<QPoint>& to_remove, QVector<QPoint>& visited) {
    int n = map_.size();
    if (x < 0 || x >= n || y < 0 || y >= n) {
      return;
    }
    if (map_[x][y] != color) {
      return;
    }
    if (std::find(visited.begin(), visited.end(), QPoint(x, y)) != visited.end()) {
      return;
    }

    // 将当前块加入到已访问列表中
    visited.append(QPoint(x, y));

    // 搜索四联通块
    dfs(x - 1, y, color, to_remove, visited);
    dfs(x + 1, y, color, to_remove, visited);
    dfs(x, y - 1, color, to_remove, visited);
    dfs(x, y + 1, color, to_remove, visited);

    // 将当前块加入到可消除列表中
    to_remove.append(QPoint(x, y));
  }

  void fillBlank() {
    int n = map_.size();
    for (int j = 0; j < n; ++j) {
      for (int i = n - 1; i >= 0; --i) {
        if (map_[i][j] == -1) {
          // 找到第一个非空格子
          int k = i - 1;
          while (k >= 0 && map_[k][j] == -1) {
            --k;
          }
          if (k >= 0) {
            // 将非空格子往下移动
            map_[i][j] = map_[k][j];
            map_[k][j] = -1;
          } else {
            // 随机生成一个新格子的颜色
            map_[i][j] = qrand() % 5;
          }
        }
      }
    }
  }

  void gameLoop() {
    if (isGameOver()) {
      // 游戏结束
      qDebug() << "Game Over!";
      qDebug() << "Final Score:" << score_;
      qApp->quit();
    } else {
      // 继续游戏
      QTimer::singleShot(0, this, &XxGame::gameLoop);
    }
  }

  bool isGameOver() {
    int n = map_.size();
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        int color = map_[i][j];
        if (color != -1) {
          // 搜索四联通块
          QVector<QPoint> to_remove;
          QVector<QPoint> visited;
          dfs(i, j, color, to_remove, visited);
          if (to_remove.size() >= 2) {
            // 存在可消除块，游戏未结束
            return false;
          }
        }
      }
    }
    return true;
  }

private:
  QVector<QVector<int>> map_;
  QMap<int, QColor> colors_{
    {0, Qt::red},
    {1, Qt::green},
    {2, Qt::blue},
    {3, Qt::yellow},
    {4, Qt::cyan},
  };
  int score_ = 0;
};

int main(int argc, char* argv[]) {
  QApplication app(argc, argv);
  qsrand(QTime::currentTime().msec());

  XxGame game;
  game.show();

  return app.exec();
}

#include "main.moc"

这个示例程序使用了Qt的QVector类来存储游戏地图，使用QMap类来存储每个格子的颜色和对应的Qt颜色对象，使用QTimer类来实现游戏主循环。在游戏主循环中，每隔一段时间就检测一次游戏是否结束，如果游戏未结束就继续游戏，否则就输出最终得分并退出游戏。