刷题日记——BFS：离开迷宫最短时间、生化武器（天津大学/南开大学机试）

例题

在这里插入图片描述

分析

需要注意地图的输入，每一行都有个换行符，需要扔掉
写完地图的输入，最好输出一下验证一下输入的对不对
由于是求最短的时间，BFS第一次找到终点就输出即可
考虑到连续输入多个样例的可能性，如果选择找到终点就输出，应该要把队列定义在每次地图输入的操作执行里面，如果定义在全局，那么上一次找到最短时间时可能没有全部出队，这样会导致错误发生

代码

#include <cstdio>
#include <map>
#include <string>
#include <string.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <limits.h>
using namespace std;

char field[101][101];
bool visited[101][101];
int direct_x[4]={-1,1,0,0};
int direct_y[4]={0,0,-1,1};

struct position{
  int x;
  int y;
  int time;
};



int main(){
  int h,w;
  while(true){
    scanf("%d%d",&h,&w);
    if(h==0&&w==0){
      break;
    }
    //开始初始化BFS
    position start;
    queue<position> instructor;

    for(int i=1;i<=h;i++){
      for(int j=0;j<=w;j++){
        scanf("%c",&field[i][j]);
        visited[i][j]=false;
        if(field[i][j]=='S'){
          start.x = i;
          start.y = j;
          visited[i][j]=true;
        }
      }
    }
    /*
    for(int i=1;i<=h;i++){
      for(int j=1;j<=w;j++){
        printf("%c",field[i][j]);
      }
      printf("\n");
    }
    */
    //继续初始化BFS
    start.time=0;
    instructor.push(start);

    bool flag = false;

    while(instructor.empty()!=true){
      int x = instructor.front().x;
      int y = instructor.front().y;
      if(field[x][y]=='E'&&flag==false){
        printf("%d\n",instructor.front().time);
        flag = true;
        break;
      }
      for(int i=0;i<4;i++){
        int temp_x = x+direct_x[i];
        int temp_y = y+direct_y[i];
        if((field[temp_x][temp_y]=='*'||field[temp_x][temp_y]=='E')&&visited[temp_x][temp_y]==false){
          position temp;
          temp.x = temp_x;
          temp.y = temp_y;
          temp.time = instructor.front().time+1;
          instructor.push(temp);
          visited[temp_x][temp_y]=true;
        }
      }
      instructor.pop();
    }
    if(flag==false){
      printf("-1\n");
    }
  }
	return 0;
}

例题——生化武器

在这里插入图片描述

分析

同样是BFS
注意退出BFS的条件，即队首位置的时间与所要计的时间一样
卡题卡了10分钟没AC，原因竟然是输出没有隔一行！！！！！！注意要看清题目啊！！！！

代码

#include <cstdio>
#include <map>
#include <string>
#include <string.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <limits.h>
using namespace std;

char field[101][101];
bool visited[101][101];
int direct_x[4]={-1,1,0,0};
int direct_y[4]={0,0,-1,1};

struct position{
  int x;
  int y;
  int time;
};



int main(){
  int n,m,t;
  while(scanf("%d%d%d",&n,&m,&t)!=EOF){
    	char bin;
    scanf("%c",&bin);//把回车扔掉

    //BFS初始化
    position start;//定义起点
    queue<position> instructor;

    for(int i=1;i<=n;i++){
      for(int j=1;j<=m+1;j++){
        char temp;
        scanf("%c",&temp);
        if(temp=='\n'){
          break;//把回车扔掉
        }
        field[i][j]=temp;
        visited[i][j]=false;
        if(temp=='*'){
          start.x = i;
          start.y = j;
          field[i][j]='#';
          visited[i][j]=true;
        }
      }
    }

    //测试：输入是否正确接收？
    //这个在后面输出还有用
    /*for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++){
        printf("%c",field[i][j]);
      }
      printf("\n");
    }*/

    //对起始位置进一步初始化
    start.time = 0;
    instructor.push(start);
    int flag=false;
    while(instructor.empty()!=true){
      int x = instructor.front().x;
      int y = instructor.front().y;
      int time = instructor.front().time;
      if(time==t){
        flag = true;
        break;
      }
      for(int i=0;i<4;i++){
        int temp_x = x+direct_x[i];
        int temp_y = y+direct_y[i];
        if(field[temp_x][temp_y]=='.'&&visited[temp_x][temp_y]==false){
          field[temp_x][temp_y]='#';
          visited[temp_x][temp_y]=true;
          position temp;
          temp.x = temp_x;
          temp.y = temp_y;
          temp.time = time+1;
          instructor.push(temp);
        }
      }
      instructor.pop();
    }
    if(flag==true){
      for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
          printf("%c",field[i][j]);
        }
        printf("\n");
      }
		printf("\n");
    }else{
      printf("No\n");
    }

  }
	return 0;
}