题目链接: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;
}