牛客寒假算法基础集训营4 C. Applese走迷宫(bfs)

题目链接：https://ac.nowcoder.com/acm/contest/330/C

       其实就是一个简单的bfs，只不过多了一个标记，结构体中多开一个变量用来记录当前的状态，然后在搜索的时候单独判断一下遇到'@'的情况就好了(将切换状态和不变都扔入队列中)，剩下的就是一个简单的bfs...

AC代码：

#include <bits/stdc++.h>
#define maxn 110
using namespace std;
struct Node{
  int x,y,sta,step;
}Now,S,Next,T;
string str[maxn];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
bool vis[maxn][maxn][2];
int n,m;

bool Check(int x, int y, int z){
  if(x < 0 || y < 0 || x >= n || y >= m)return false;
  if(str[x][y] == '#') return false;
  if(vis[x][y][z] == true) return false;
  if((z == 0 && str[x][y] == 'w') || (z == 1 && str[x][y] == '~')) return false;
  return true;
}

int bfs(){
  queue<Node> q;
  memset(vis,false,sizeof(vis));
  S.sta = 0;
  S.step = 0;
  q.push(S);
  while(!q.empty()){
    Now = q.front();
    q.pop();
    if(Now.x == T.x && Now.y == T.y){
      return Now. step;
    }
    if(str[Now.x][Now.y] == '@' && vis[Now.x][Now.y][Now.sta ^ 1] == false){
      Next.x = Now.x; Next.y = Now.y; Next.sta = Now.sta ^ 1;
      Next.step = Now.step + 1;
      vis[Next.x][Next.y][Next.sta] = true;
      q.push(Next);
    }
    for(int i=0;i<4;i++){
      Next.x = Now.x + dir[i][0];
      Next.y = Now.y + dir[i][1];
      if(Check(Next.x, Next.y, Now.sta)){
        Next.sta = Now.sta;
        Next.step = Now.step + 1;
        vis[Next.x][Next.y][Next.sta] = true;
        q.push(Next);
      }
    }
  }
  return -1;
}

int main()
{
  scanf("%d%d",&n,&m);
  for(int i=0;i<n;i++){
    cin>>str[i];
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(str[i][j] == 'S'){
        S.x = i; S.y = j;
      }
      if(str[i][j] == 'T'){
        T.x = i; T.y = j;
      }
    }
  }
  int ans = bfs();
  printf("%d\n", ans);
  return 0;
}