链接：https://ac.nowcoder.com/acm/contest/330/C
来源：牛客网
题目描述
在这个游戏中，它被困在了一个 n×mn×m 的迷宫中，它想要逃出这个迷宫。
在迷宫中，有一些方格是水池，只有当 Applese 处于水属性的时候才可以通过；有一些方格是岩浆，只有当 Applese 是火属性的时候可以通过；有一些方格是墙壁，无论如何都无法通过；另一些格子是空地（包括起点和终点），可以*通过。
在一些空地上有神秘道具可以让 Applese 转换自己的属性（从水属性变为火属性或从火属性变为水属性，需要一个单位的时间）。
输入描述:
第一行两个正整数 n, m 表示迷宫的大小。
接下来 n 行，每行长度为 m 的字符串。描述地图。
其中 ‘S‘ 表示起点，‘T‘ 表示终点，‘.‘ 表示空地，‘w‘表示岩浆，‘~‘表示水池，‘@‘ 表示道具，‘#‘表示障碍。
保证地图中的起点和终点只有一个，道具都位于空地。
输出描述:
输出一个整数，表示 Applese 走出迷宫的最短时间。特别地，如果 Applese 走不出迷宫，输出 "-1"。
示例1
输入
5 5 .w@.. .S#.. ~w#.. .w..~ @w.~T
输出
18
备注:
1≤n,m≤100
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<queue> #define ll long long #define inf 0x3f3f3f3f using namespace std; int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//右 上 左 下 int n,m; char a[105][105]; bool vis[105][105][2]; int ans; struct node { int x; int y; int sta;//属性，水属性为0，火属性为1 int time; }; node s;//起点 int ex,ey; queue<node>que; void bfs() { while(!que.empty()) que.pop(); s.sta=0;s.time=0;//初始状态和初始时间 que.push(s); vis[s.x][s.y][s.sta]=true; while(!que.empty()) { node now=que.front(); que.pop(); if(now.x==ex && now.y==ey) { ans=now.time; return; } for(int i=0;i<4;i++)///不改变状态走 { int tx=now.x+d[i][0]; int ty=now.y+d[i][1]; if( tx>=0 && tx<n && ty>=0 && ty<m && a[tx][ty]!=‘#‘ && !vis[tx][ty][now.sta]) {///下一步没越界 并且不是障碍 并且没被走过 if( (a[tx][ty]==‘w‘ && now.sta==0) || (a[tx][ty]==‘~‘ && now.sta==1) ) continue;///属性相异，不能走，看其他方向 else { vis[tx][ty][now.sta]=true; que.push( node{tx,ty,now.sta,now.time+1} ); } } } if(a[now.x][now.y]==‘@‘ && !vis[now.x][now.y][now.sta^1]) {///遇到道具 并且 并且之前没有以另一种状态走到这里,改变状态 vis[now.x][now.y][now.sta^1]=true; que.push( node{now.x,now.y,now.sta^1,now.time+1} ); } } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) scanf("%s",a[i]); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(a[i][j]==‘S‘) {s.x=i;s.y=j;} if(a[i][j]==‘T‘) {ex=i;ey=j;} } } memset(vis,false,sizeof(vis)); ans=-1; bfs(); printf("%d\n",ans); } return 0; }