图结构的应用
c++ 编程语言
图结构的应用
c++ 编程语言

图结构的应用

前言

图结构在计算机科学及众多领域中具有极其重要的地位，说到图就不得不提起两种核心搜索算法-BFS和DFS，

DFS主要通过从一个顶点开始并一直深入直至尽头，然后再搜索另一个顶点，通常以递归和栈的方式实现；

BFS则主要通过队列的方式先搜查最先进入队列的点，以“先进先出”为原则。

立意

扫雷作为一款几乎人人玩过的小游戏，选择去做这个是想重温经典

image-20250525093628285

问题描述

->未探索 0-8->附近的雷数 !->标记点 9->雷

输入：

生成雷的数量

1->扫雷，2->标记

横坐标x ,纵坐标Y

输出：

对应的图

开始的图

image-20250525094842912

样例输入：1 2 1

image-20250525094656955

实验思路

创建两个二维矩阵来存放两个地图:玩家视角的地图和地图的原图，可以通过地图的原图来为玩家视角地图做分析。

创建原图：用两个一位数组储存x,y的偏移量，通过BFS遍历计算原图中每个格子周围的地雷数(这里其实可以直接用双重循环来遍历每个格子，效率更高，只是想练习一下BFS)；

双重循环:

void initMap(int map[MAX][MAX],int boomNum){
  int i,j,z,x,y;
  int a[8]={-1,-1,-1,0,1,1,1,0};
  int b[8]={-1,0,1,1,1,0,-1,-1};
  srand((unsigned int)time(NULL));
  for(i=0;i<MAX;++i)
  for(j=0;j<MAX;++j)
  map[i][j]=0;
  for(z=0;z<boomNum;++z){
    i=rand()%MAX;
    j=rand()%MAX;
    if(map[i][j]==9)
    ++boomNum;
    else
    map[i][j]=9;
  }
  for(i=0;i<MAX;i++)
  for(j=0;j<MAX;j++){
    if(map[i][j]==9)
    continue;
    for(z=0;z<8;z++){
      x=i+a[z];
      y=j+b[z];
      if(x>0&&x<MAX&&y>0&&y<MAX&&map[x][y]==9)
      ++map[i][j];
    }
  }

BFS:

void initMap(int map[MAX][MAX],int boomNum){
  int i,j,z,x=0,y=0;
  int visited[21][21];
  memset(visited,0,sizeof(visited));
  queue<pair<int,int>>que;
  int a[8]={-1,-1,-1,0,1,1,1,0};
  int b[8]={-1,0,1,1,1,0,-1,-1};
  srand((unsigned int)time(NULL));
  for(i=0;i<MAX;++i)
  for(j=0;j<MAX;++j)
  map[i][j]=0;
  for(z=0;z<boomNum;++z){
    i=rand()%MAX;
    j=rand()%MAX;
    if(map[i][j]==9)
    ++boomNum;
    else
    map[i][j]=9;
  }
  for(int i=0;i<MAX;++i)
  for(int j=0;j<MAX;++j){
    if(map[i][j]==0){
      x=i;
      y=j;
      break;
    }
  }
  visited[x][y]=1;
  que.push(make_pair(x,y));
  while(!que.empty()){
    for(int i=0;i<8;i++){
      int nx=que.front().first+a[i];
      int ny=que.front().second+b[i];
       if(nx>=0&&nx<MAX&&ny>=0&&ny<MAX&&visited[nx][ny]==0){
        if(map[nx][ny]==9)
       map[que.front().first][que.front().second]+=1;
       else{
        visited[nx][ny]=1;
       que.push(make_pair(nx,ny));}
       }
    }
    que.pop();
  }
}

使用种子函数srand()，以时间为变量，通过伪随机对雷进行分布；

创建玩家视角地图:如果格子在原图中对应9，则输出‘#’，如果对应-1，则输出‘!’

DFS遍历格子的四个方向，如果对应格子数不为零，则赋值并返回，否则继续遍历。

最后判断胜利条件。

实验代码

#include<bits/stdc++.h>
#include<time.h>
#include<stdlib.h>
#define MAX 20
using namespace std;
void initMap(int map[MAX][MAX],int boomNum){
  int i,j,z,x=0,y=0;
  int visited[21][21];
  memset(visited,0,sizeof(visited));
  queue<pair<int,int>>que;
  int a[8]={-1,-1,-1,0,1,1,1,0};
  int b[8]={-1,0,1,1,1,0,-1,-1};
  srand((unsigned int)time(NULL));
  for(i=0;i<MAX;++i)
  for(j=0;j<MAX;++j)
  map[i][j]=0;
  for(z=0;z<boomNum;++z){
    i=rand()%MAX;
    j=rand()%MAX;
    if(map[i][j]==9)
    ++boomNum;
    else
    map[i][j]=9;
  }
  for(int i=0;i<MAX;++i)
  for(int j=0;j<MAX;++j){
    if(map[i][j]==0){
      x=i;
      y=j;
      break;
    }
  }
  visited[x][y]=1;
  que.push(make_pair(x,y));
  while(!que.empty()){
    for(int i=0;i<8;i++){
      int nx=que.front().first+a[i];
      int ny=que.front().second+b[i];
       if(nx>=0&&nx<MAX&&ny>=0&&ny<MAX&&visited[nx][ny]==0){
        if(map[nx][ny]==9)
       map[que.front().first][que.front().second]+=1;
       else{
        visited[nx][ny]=1;
       que.push(make_pair(nx,ny));}
       }
    }
    que.pop();
  }
}
void initPlayerViewMap(int playerviewmap[MAX][MAX]){
  int i,j;
  for(i=0;i<MAX;i++)
  for(j=0;j<MAX;j++){
    playerviewmap[i][j]=9;
  }
}
void printViewMap(int  playerviewmap[MAX][MAX],int map[MAX][MAX]){
  int i,j,a=0;
  char ch='#',ch1='!';
  printf("%6d",a);
  for(i=1;i<MAX;i++){
    printf("%4d",i);
  }
  cout<<endl;
  for(i=0;i<MAX;++i){
    printf("%2d",i);
    for(j=0;j<MAX;++j){
      if(playerviewmap[i][j]==9)
      printf("%4c",ch);
      else if(playerviewmap[i][j]==-1)
      printf("%4c",ch1);
      else
      printf("%4d",map[i][j]);
    }
    cout<<endl;
  }
  cout<<"选项:1->扫雷 0->标记"<<endl;
}
void pathFinding(int i,int j,int playerviewmap[MAX][MAX],int map[MAX][MAX]){

    if(i < 0 || i >= MAX || j < 0 || j >= MAX|| playerviewmap[i][j] == 0) return ;
  playerviewmap[i][j] = map[i][j];
    if(map[i][j] != 0) return ;
  pathFinding(i-1,j,playerviewmap,map);
  pathFinding(i,j+1,playerviewmap,map);
  pathFinding(i+1,j,playerviewmap,map);
  pathFinding(i,j-1,playerviewmap,map);
}
bool operate_1(int i,int j,int playerviewmap[MAX][MAX],int map[MAX][MAX]){
  if(map[i][j]==9)
  return true;
  else if(map[i][j]>0&&map[i][j]<9)
  playerviewmap[i][j]=map[i][j];
  else if(map[i][j]==0)
  pathFinding(i,j,playerviewmap,map);
  return false;
}
void opearte_0(int i,int j,int playerviewmap[MAX][MAX]){
  if(playerviewmap[i][j]==-1)
  playerviewmap[i][j]=9;
  else if(playerviewmap[i][j]==9)
  playerviewmap[i][j]=-1;
}
bool isWin(int playerviewmap[MAX][MAX],int map[MAX][MAX]){
  int i,j;
  for(i=0;i<MAX;i++)
  for(j=0;j<MAX;j++)
  if(map[i][j]!=9&&(playerviewmap[i][j]==9||playerviewmap[i][j]==-1))
  return false;
  return true;
}
void printMap(int map[MAX][MAX]){
  int i,j,a=0;
  printf("%6d",a);
  for(i=1;i<MAX;i++){
    printf("%4d",i);
  }
  cout<<endl;
  for(i=0;i<MAX;++i){
    printf("%2d",i);
    for(j=0;j<MAX;++j){
      printf("%4d",map[i][j]);
    }
    cout<<endl;
}
}
int main(){
  int map[MAX][MAX];
  int playerviewmap[MAX][MAX];
  int i,j,boomNum,operate;
  bool lose=false;
  cout<<"#->未探索 0-8->附近的雷数 !->标记点 9->雷"<<endl;
  cout<<"请输入要生成的雷的数量:";
  cin>>boomNum;
  initMap(map,boomNum);
  initPlayerViewMap(playerviewmap);
  system("cls");
  while(true){
    printViewMap(playerviewmap,map);
    cout<<"请输入序号以及要操作的点位坐标";
    cin>>operate>>i>>j;
    if(operate==1)
    lose=operate_1(i,j,playerviewmap,map);
    else if(operate==0)
    opearte_0(i,j,playerviewmap);
    if(lose)
    break;
    if(isWin(playerviewmap,map))
    break;
    system("cls");
  }
  system("cls");
  printMap(map);
  if(lose)
  cout<<"你输了!"<<endl;
  else
  cout<<"你赢了!"<<endl;
  system("pause");
  return 0;
}

心得体会

做这样一个简单小应用需要了解许多相应的知识，开始可以先借鉴别人的思路，读懂代码的每一步，包括逻辑功能，函数功能，每一步是怎样实现的，一开始是比较困难的，但只要理解了代码的思路，学会了相应函数的应用，掌握了做这个游戏的基本知识，就会容易一些，这需要平时的多加练习，在他人的思路上建立起自己的思路，然后实现出来，每天必须抽出时间敲代码，只有这样代码水平才能逐渐提高，课堂上的一些算法必须手动敲出来才能理解到底是怎样进行的。

相关条目

  • BFS经典题目
  • DP动态规划
  • 贪心算法

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注