1 条题解
-
0
和走迷宫类似的广搜,难点在于对传送点的处理,一旦走到一个传送点,马上将坐标移动到另一个传送点
#include<bits/stdc++.h> using namespace std; const int N=305; int n,m,k,s,t,a[N][N],d[N][N],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; int ex,ey,sx,sy; pair<int,int> h[200];//A h['A'] h['A'+26] char c[N][N]; queue<pair<int,int>> q; int bfs(int sx,int sy){ memset(d,0x3f,sizeof(d)); d[sx][sy]=0; q.push({sx,sy}); while (!q.empty()){ int x=q.front().first; int y=q.front().second; q.pop(); if (x==ex && y==ey) return d[x][y]; for (int i=0;i<4;++i){ int _x=x+dx[i]; int _y=y+dy[i]; char ch=c[_x][_y]; if (_x>=1 && _x<=n && _y>=1 && _y<=m && ch!='#'){ if (ch>='A' && ch<='Z') { if (h[ch]==make_pair(_x,_y)) _x=h[ch+26].first,_y=h[ch+26].second; else _x=h[ch].first,_y=h[ch].second; } if (d[_x][_y]>d[x][y]+1) { d[_x][_y]=d[x][y]+1; q.push({_x,_y}); } } } } return -1; } int main(){ // freopen("in.txt","r",stdin); int x,y; cin>>n>>m; for (int i=1;i<=n;++i){ cin>>c[i]+1; for (int j=1;j<=m;++j) if (c[i][j]=='@') sx=i,sy=j; else if (c[i][j]=='=') ex=i,ey=j; else if (c[i][j]>='A' && c[i][j]<='Z'){ if (h[c[i][j]]==make_pair(0,0)) h[c[i][j]]={i,j}; else h[c[i][j]+26]={i,j}; } } cout<<bfs(sx,sy); }
- 1
信息
- ID
- 767
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 8
- 标签
- 递交数
- 183
- 已通过
- 34
- 上传者