题意
给定一个10*10以内的地图，和p(P<=30000)只老鼠，给定其出现位置和时间T(T<=1,000,000,000)，求最多抓到几只老鼠。
题解
代码
代码语言：javascript复制#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 30005
#define inf 0x3f3f3f3f
using namespace std;
struct node{int x,y,t;}a[N];
int n,m,p;
int f[N],ans;//经过第i个最多经过几个
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int mm[20][20];
int dis[20][20][20][20];
bool cmp(const node& a,const node& b){
return a.t<b.t;
}
void bfs(int x,int y){
dis[x][y][x][y]=0;
queue<node>q;
q.push((node){x,y});
while(!q.empty()){
node k=q.front();
q.pop();
for(int i=0;i<4;i ){
int nx=k.x dx[i],ny=k.y dy[i];
if(nx>=0&&ny>=0&&nx<n&&ny<m&&mm[nx][ny]
&&dis[x][y][nx][ny]==inf){
dis[x][y][nx][ny]=dis[x][y][k.x][k.y] 1;
q.push((node){nx,ny});
}
}
}
}
int main() {
while(~scanf("%d%d",&n,&m)){
memset(f,-inf,sizeof f);
memset(dis,inf,sizeof dis);
f[0]=ans=0;
for(int i=0;i<n;i )
for(int j=0;j<m;j ){
char c;
scanf(" %c",&c);mm[i][j]=(c!='#');
if(c=='L')a[0]=(node){i,j,0};
}
for(int i=0;i<n;i )
for(int j=0;j<m;j )if(mm[i][j])bfs(i,j);
scanf("%d",&p);
for(int i=1;i<=p;i ){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
a[i].x--;a[i].y--;
}
sort(a 1,a 1 p,cmp);
for(int i=1;i<=p;i ){
for(int j=max(i-50,0);j<i;j ){
if(f[j]!=-inf&&dis[a[j].x][a[j].y][a[i].x][a[i].y]<=a[i].t-a[j].t)
f[i]=max(f[i],f[j] 1);
}
ans=max(f[i],ans);
}
printf("%dn",ans);
}
return 0;
}
