1 条题解
-
0
#pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> using namespace std; inline int read() { char ch=getchar(); int x=0,m=1; while(!isdigit(ch)){ if (ch=='-') m=-1; ch=getchar(); } while(isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); } return x*m; } inline void write(int x) { if (x<0) putchar('-'),x=-x; if (x>9) write(x/10); putchar(x%10+'0'); } int n,m; struct Node{ int x,y,z; }f[10010]; short dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0}; bool p[110][110]; inline int bfs(int x1,int y1,int x,int y) { int h(0),t(1); f[1].x=x1;f[1].y=y1; while(h<t){ ++h; if (f[h].x==x&&f[h].y==y) return f[h].z; for (int i=1;i<=4;i++){ int xx(dx[i]+f[h].x),yy(dy[i]+f[h].y); if (p[xx][yy]==false) continue; f[++t].x=xx; f[t].y=yy; f[t].z=f[h].z+1; } } return -1; } signed main() { n=read(),m=read(); char ch(getchar()); int x1,y1,x2,y2; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){ while(ch!='S'&&ch!='T'&&ch!='.'&&ch!='#') ch=getchar(); if (ch=='S') x1=i,y1=j,p[i][j]=true; else if (ch=='T') x2=i,y2=j,p[i][j]=true; else if (ch=='.') p[i][j]=true; ch=getchar(); } write(bfs(x1,y1,x2,y2)); return 0; }
- 1
信息
- ID
- 173
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 51
- 已通过
- 33
- 上传者