2 条题解
-
0yejun LV 10 MOD @ 2019-01-24 11:45:50
/* */ #define method_1 #ifdef method_1 /* 第一问可以用二分答案 第二问在二分答案的基础上bfs 为了方便起见,可以在开始位置用bfs预处理出每个点最近的守卫的距离 */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<map> #include<vector> #define ll long long using namespace std; int ans1,ans2; int head,tail; int n,X,Y; int x1,y1,x2,y2; int mp[1005][1005]; int x[1000005],y[1000005],step[1000005]; bool vis[1005][1005]; int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1}; void pre() { while(head!=tail) { int nx=x[head],ny=y[head];head++; for(int k=0;k<4;k++) { int tx=nx+xx[k],ty=ny+yy[k]; if(tx>=X||ty>=Y||tx<0||ty<0||mp[tx][ty]!=-1)continue; mp[tx][ty]=mp[nx][ny]+1; x[tail]=tx;y[tail]=ty;tail++; } } } int bfs(int val) { head=0;tail=1; if(x1==x2&&y1==y2)return 0; memset(vis,0,sizeof(vis)); vis[x1][y1]=1;x[0]=x1;y[0]=y1; while(head!=tail) { int nx=x[head],ny=y[head],ns=step[head];head++; for(int k=0;k<4;k++) { int tx=nx+xx[k],ty=ny+yy[k]; if(tx>=X||ty>=Y||tx<0||ty<0||mp[tx][ty]<val||vis[tx][ty])continue; vis[tx][ty]=1; if(tx==x2&&ty==y2)return ns+1; x[tail]=tx;y[tail]=ty;step[tail]=ns+1;tail++; } } return -1; } int main() { ios::sync_with_stdio(false); // freopen("赠邻女(寄李亿员外).in","r",stdin); memset(mp,-1,sizeof(mp)); cin>>n>>X>>Y; cin>>x1>>y1>>x2>>y2; int a,b; for(int i=1;i<=n;i++) { cin>>a>>b; mp[a][b]=0; x[tail]=a;y[tail]=b;tail++; } pre(); int l=0,r=mp[x1][y1]; while(l<=r) { int mid=(l+r)>>1; int t=bfs(mid); if(t==-1)r=mid-1; else l=mid+1,ans1=mid,ans2=t; } cout<<ans1<<" "<<ans2; return 0; } #endif #ifdef method_2 /* */ #endif #ifdef method_3 /* */ #endif
-
-12021-03-13 13:56:49@
/*
/
#define method_1
#ifdef method_1
/
第一问可以用二分答案
第二问在二分答案的基础上bfs为了方便起见,可以在开始位置用bfs预处理出每个点最近的守卫的距离
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<vector>
#define ll long long
using namespace std;int ans1,ans2;
int head,tail;
int n,X,Y;
int x1,y1,x2,y2;
int mp[1005][1005];
int x[1000005],y[1000005],step[1000005];
bool vis[1005][1005];
int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
void pre()
{
while(head!=tail)
{
int nx=x[head],ny=y[head];head++;
for(int k=0;k<4;k++)
{
int tx=nx+xx[k],ty=ny+yy[k];
if(tx>=X||ty>=Y||tx<0||ty<0||mp[tx][ty]!=-1)continue;
mp[tx][ty]=mp[nx][ny]+1;
x[tail]=tx;y[tail]=ty;tail++;
}
}
}
int bfs(int val)
{
head=0;tail=1;
if(x1==x2&&y1==y2)return 0;
memset(vis,0,sizeof(vis));
vis[x1][y1]=1;x[0]=x1;y[0]=y1;
while(head!=tail)
{
int nx=x[head],ny=y[head],ns=step[head];head++;
for(int k=0;k<4;k++)
{
int tx=nx+xx[k],ty=ny+yy[k];
if(tx>=X||ty>=Y||tx<0||ty<0||mp[tx][ty]<val||vis[tx][ty])continue;
vis[tx][ty]=1;
if(tx==x2&&ty==y2)return ns+1;
x[tail]=tx;y[tail]=ty;step[tail]=ns+1;tail++;
}
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);
// freopen("赠邻女(寄李亿员外).in","r",stdin);
memset(mp,-1,sizeof(mp));
cin>>n>>X>>Y;
cin>>x1>>y1>>x2>>y2;
int a,b;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
mp[a][b]=0;
x[tail]=a;y[tail]=b;tail++;
}
pre();
int l=0,r=mp[x1][y1];
while(l<=r)
{
int mid=(l+r)>>1;
int t=bfs(mid);
if(t==-1)r=mid-1;
else l=mid+1,ans1=mid,ans2=t;
}
cout<<ans1<<" "<<ans2;
return 0;
}
#endif
#ifdef method_2
/**/
#endif
#ifdef method_3
/**/
#endif
- 1
信息
- 难度
- 7
- 分类
- (无)
- 标签
- (无)
- 递交数
- 45
- 已通过
- 8
- 通过率
- 18%
- 被复制
- 3
- 上传者