【bfs,字首和優化】Day 10 提高組模擬C組 T4 城市統計

NO IMAGE

題目大意

給定一些點,每個點的值為距離它最近的1的點的曼哈頓距離,求出所有點與它周邊不超過r” role=”presentation”>rrr行r” role=”presentation”>rrr列的值

解題思路

首先我們看到這題的資料範圍,用黃*邦想都知道這是一個n3″ role=”presentation”>n3n3n^3能過的題,所以我就xjb” role=”presentation”>xjbxjbxjb亂打了一個廣搜,然後用字首和xjb” role=”presentation”>xjbxjbxjb維護一下行列就過了。
還有一種是用字首和維護矩陣,好像是n2″ role=”presentation”>n2n2n^2,只能%一%,然後就直接扣程式碼了

n3″ role=”presentation”>n3n3n^3程式碼

SRC Download 
#include<queue>
#include<cstdio>
#include<algorithm>
#define r(i,a,b) for(register int i=a;i<=b;i  )
using namespace std;int t,n,r,s[151][151],a[151][151],ans;
const short dx[4]={-1,0,1,0};
const short dy[4]={0,1,0,-1};
bool d[151][151];
struct node{int x,y,s;};
int bfs(node start)
{
if(d[start.x][start.y]) return 0;
queue<node>q;bool vis[151][151]={0};
q.push(start);vis[start.x][start.y]=true;
while(q.size())
{
node x=q.front();q.pop();
r(i,0,3)
{
node y=(node){x.x dx[i],x.y dy[i],x.s 1};
if(y.x<1||y.y<1||y.x>n||y.y>n) continue;
if(vis[y.x][y.y]) continue;
if(d[y.x][y.y]) return y.s;
q.push(y);
vis[y.x][y.y]=true;
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&r);
r(i,1,n) r(j,1,n) scanf("%d",&d[i][j]);
r(i,1,n) r(j,1,n) a[i][j]=bfs((node){i,j,0}),s[i][j]=s[i][j-1] a[i][j];//字首和維護
r(i,1,n) 
{
r(j,1,n)
{
ans=0;
r(k,max(i-r,0),min(i r,n)) ans =s[k][min(j r,n)]-s[k][max(j-r-1,0)];
printf("%d ",ans);
}
putchar(10);
}
putchar(10);
}
}

n2″ role=”presentation”>n2n2n^2程式碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
using namespace std;
inline LL read() {
LL d=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){d=d*10 s-'0';s=getchar();}
return d*f;
}
queue<int>x,y;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int f[151][151],ans[151][151],c[151][151];
int n;
void bfs()
{
while(!x.empty())
{
for(int i=0;i<4;i  )
{
int xx=x.front() dx[i],yy=y.front() dy[i];
if(xx<1||yy<1||xx>n||yy>n||c[xx][yy]==1) continue;
c[xx][yy]=1;
f[xx][yy]=f[x.front()][y.front()] 1;
x.push(xx);y.push(yy);
}
x.pop();y.pop();
}
return;
}
int main()
{   
int t=read(),a,bx,by,sx,sy;
for(int i=1;i<=t;i  )
{
memset(f,0,sizeof(f));
memset(ans,0,sizeof(ans));
n=read();int r=read();
for(int i=1;i<=n;i  )
for(int j=1;j<=n;j  )
{
c[i][j]=read();
if(c[i][j]) x.push(i),y.push(j);
}
bfs();
for(int i=1;i<=n;i  )
for(int j=1;j<=n;j  )
ans[i][j]=ans[i-1][j] ans[i][j-1] f[i][j]-ans[i-1][j-1];//字首和維護
for(int i=1;i<=n;i  )
{
for(int j=1;j<=n;j  )
{
bx=min(n,i r);by=min(n,j r);
sx=max(0,i-r-1);sy=max(0,j-r-1);
printf("%d ",ans[bx][by]-ans[bx][sy]-ans[sx][by] ans[sx][sy]);
}
printf("\n");
}
printf("\n");
}
return 0;
}