maze

题意:走迷宫,每次可以上下左右的走,花费为1s,或者当前位置有传送阵,花费为3s
题解:搜索,对于每个点进行上下左右的压入搜索,然后对于每个点的传送阵进行压入的搜索......
广搜裸题
记得标记路径防止重复

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define ll long long
#define N 405
using namespace std;
const int dx[5]={1,-1,0,0},dy[5]={0,0,1,-1};
int n,m,f[N][N],ex,ey,sx,sy,q,u1[N*3],v1[N*3];
char ch;
char a[N][N];
struct he{
    int u,v,t;
}b[N][N];
queue<he>Q;
void bfs(int sx,int sy){
    int ans=10000000;
    while(!Q.empty()) Q.pop();
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) f[i][j]=10000000;
    f[sx][sy]=0;
    Q.push((he){sx,sy,0});
    while(!Q.empty()){
        he p=Q.front();Q.pop();
        if(p.u==ex&&p.v==ey) {
            ans=min(ans,p.t);
            continue;
        }
        if(b[p.u][p.v].u!=-1){
            int x1=b[p.u][p.v].u;
            int y1=b[p.u][p.v].v;
            if(a[x1][y1]!='#'&&f[x1][y1]>p.t+3){
                f[x1][y1]=p.t+3;
                Q.push((he){x1,y1,p.t+3});
            }
        }
        for(int i=0;i<4;i++){
            int x1=p.u+dx[i];
            int y1=p.v+dy[i];
            if(x1<n&&x1>=0&&y1>=0&&y1<m&&a[x1][y1]!='#'&&f[x1][y1]>p.t+1){
                f[x1][y1]=p.t+1;
                Q.push((he){x1,y1,p.t+1});
            }
        }
    }
    if(ans!= 10000000)
    printf("%d\n",ans);else printf("-1\n");
}
int main(){
    //freopen("1.in","r",stdin);
    for(int i=0;i<=300;i++)
        for(int j=0;j<=300;j++) b[i][j].u=b[i][j].v=-1;
    while(scanf("%d%d%d",&n,&m,&q)!=EOF){
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                scanf("%c",&ch);
                while(ch!='.'&&ch!='S'&&ch!='T'&&ch!='#') ch=getchar();
                a[i][j]=ch;
                if(ch=='S') sx=i,sy=j;
                if(ch=='T') ex=i,ey=j;
            }
        for(int i=1;i<=q;i++){
            scanf("%d%d",&u1[i],&v1[i]);
            scanf("%d%d",&b[u1[i]][v1[i]].u,&b[u1[i]][v1[i]].v);
        }
        bfs(sx,sy);
        for(int i=1;i<=q;i++)
            b[u1[i]][v1[i]].u=-1,b[u1[i]][v1[i]].v=-1;
    }
}