非常显然的BFS搜索
应注意的问题： 1、到了传送点必须传送，不能略过 2、传送点传送不消耗步数 3、传送点可能会经过两次 （在这里跪了好久orz） 例： 2 10 .#Q#...... L.a......a
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; int n,m,T,ans; char s[60]; int map[60][60]; bool vis[60][60]; int sx,sy,ex,ey; int a[5]={1,-1,0,0},b[5]={0,0,1,-1}; struct node_pair { int x1,x2,y1,y2; }chuan[30]; struct node { int x,y,v; }; queue <node> q; void init() { memset(map,0,sizeof(map)); memset(vis,0,sizeof(vis)); ans=0; while (!q.empty()) q.pop(); for (int i=1;i<=26;i++) { chuan[i].x1=0; chuan[i].x2=0; chuan[i].y1=0; chuan[i].y2=0; } } void bfs(int x,int y) { node t; t.x=x; t.y=y; t.v=0; vis[x][y]=true; q.push(t); while (!q.empty()) { node now=q.front(); q.pop(); if (now.x==ex && now.y==ey) { ans=now.v; break; } if (map[now.x][now.y]>0) { int num=map[now.x][now.y]; if (now.x==chuan[num].x1 && now.y==chuan[num].y1) { now.x=chuan[num].x2; now.y=chuan[num].y2; } else { now.x=chuan[num].x1; now.y=chuan[num].y1; } //vis[now.x][now.y]=true; } //printf(" %d %d %d\n",now.x,now.y,now.v); for (int i=0;i<4;i++) { int nx=now.x+a[i],ny=now.y+b[i]; if (nx>=1 && nx<=n && ny>=1 && ny<=m && map[nx][ny]>=0 && !vis[nx][ny]) { node tt; tt.x=nx; tt.y=ny; tt.v=now.v+1; if (map[nx][ny]==0) vis[nx][ny]=true; q.push(tt); } } } } void db() { for (int i=1;i<=26;i++) { printf("%d %d %d %d %d\n",i,chuan[i].x1,chuan[i].y1,chuan[i].x2,chuan[i].y2); } } int main() { scanf("%d",&T); for (int tt=1;tt<=T;tt++) { init(); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%s",s); for (int j=0;j<m;j++) { if (s[j]=='#') map[i][j+1]=-1; if (s[j]>='a' && s[j]<='z') { int t=s[j]-'a'+1; map[i][j+1]=t; if (chuan[t].x1==0) { chuan[t].x1=i; chuan[t].y1=j+1; } else { chuan[t].x2=i; chuan[t].y2=j+1; } } if (s[j]=='L') { sx=i; sy=j+1; } if (s[j]=='Q') { ex=i; ey=j+1; } } } bfs(sx,sy); if (!ans) printf("-1\n"); else printf("%d\n",ans); //db(); } return 0; }
