3 条题解
-
1
#include<bits/stdc++.h> using namespace std; #define int long long const int N=105; int n,m; int a[N][N],dis[N][N]; int dx[]={-1,-1,-1,0,0,1,1,1}; int dy[]={-1,0,1,-1,1,-1,0,1}; queue<pair<int,int> > que; bool inside(int nx,int ny){ return nx>=1&&nx<=n&&ny>=1&&ny<=m; } void bfs(int sr,int sc){ memset(dis,0x3f,sizeof(dis)); dis[sr][sc]=0; que.push({sr,sc}); while(!que.empty()){ int x=que.front().first; int y=que.front().second; que.pop(); for(int i=0;i<8;i++){ int nx=x+dx[i]; int ny=y+dy[i]; if(!inside(nx,ny)){ continue; } if(a[nx][ny]=='*'){ continue; } if(dis[x][y]+1<dis[nx][ny]){ dis[nx][ny]=dis[x][y]+1; que.push({nx,ny}); } } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int Y,X,Mx,My; cin>>Y>>X>>Mx>>My; n=X; m=Y; int sr=X-My+1; int sc=Mx; for(int i=1;i<=X;i++){ string s; cin>>s; for(int j=1;j<=Y;j++){ a[i][j]=s[j-1]; } } bfs(sr,sc); int ret=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]=='.'){ ret=max(ret, dis[i][j]); } } } cout<<ret<<endl; return 0; } //包AC的
信息
- ID
- 2816
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 121
- 已通过
- 25
- 上传者