C++11(clang++ 3.9) 解法, 执行用时: 122ms, 内存消耗: 8368K, 提交时间: 2019-07-18 20:53:15

#include<bits/stdc++.h>
using namespace std;
int n,m,k,nx,ny,st;
int a[305][305],use[305][305];
int b[305][305],cnt;
int f[100005][3];
int w[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
int g[25][25],ans;
int dp[100005][16];

int calc(int x){
	int gs=0;
	while(x){
		x-=x&-x;
		gs++;
	}
	return gs;
}

void bfs(int x,int y){
	int h=0,j=1;
	f[1][0]=x,f[1][1]=y,f[1][2]=0;
	do{
		h++;
		for(int i=0;i<4;i++){
			nx=f[h][0]+w[i][0];
			ny=f[h][1]+w[i][1];
			if(nx<=0||ny<=0||nx>n||ny>m) continue;
			if(use[nx][ny]||a[nx][ny]==1) continue;
			use[nx][ny]=1;
			f[++j][0]=nx,f[j][1]=ny;
			f[j][2]=f[h][2]+1;
			if(b[nx][ny]) g[b[x][y]][b[nx][ny]]=f[j][2];
		}
	}while(h<j);
}

int main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j]==2||(i==1&&j==1)) b[i][j]=++cnt;
		}
	}
	memset(g,63,sizeof(g));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(b[i][j]){
				memset(use,0,sizeof(use));
				bfs(i,j);
			}
		}
	}
	memset(dp,63,sizeof(dp));
	dp[1][1]=0;
	int S=1<<cnt;
	for(int i=1;i<S;i++){
		for(int j=1;j<=cnt;j++){
			for(int k=1;k<=cnt;k++){
				st=(1<<(k-1))&i;
				if(st==0) dp[i|(1<<(k-1))][k]=min(dp[i|(1<<(k-1))][k],dp[i][j]+g[j][k]);
			}
		}
	}
	ans=0;
	for(int i=1;i<S;i++){
		for(int j=1;j<=cnt;j++){
			if(dp[i][j]<=k) ans=max(ans,calc(i));
		}
	}
	printf("%d\n",ans-1);

	return 0;
}

C++14(g++5.4) 解法, 执行用时: 112ms, 内存消耗: 4580K, 提交时间: 2019-11-09 22:29:02

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int cnt=0;
int dis[30][30];
int f[310][310];
struct node
{
	int x,y;
};
int d[4][2]={0,1,0,-1,1,0,-1,0}; 
int s[400][400],a[400][400],vis[400][400];
int dp[(int)(1<<20)+10][22];
void bfs(int now,int x,int y)
{
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=0x3f3f3f3f,vis[i][j]=0;
	queue<node>q;
	q.push({x,y});
	vis[x][y]=1;
	f[x][y]=0;
	while(q.size())
	{
		node t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int xx=t.x+d[i][0],yy=t.y+d[i][1];
			if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy]||a[xx][yy]==1) continue;
			q.push({xx,yy}),vis[xx][yy]=1,f[xx][yy]=f[t.x][t.y]+1;
		}
	}
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	  if(s[i][j])
	 	 dis[now][s[i][j]]=f[i][j];
}
int main()
{
	int ans=0;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	 {
	 	cin>>a[i][j];
	 	if(a[i][j]==2)s[i][j]=++cnt;
	 }
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
		if(s[i][j]) bfs(s[i][j],i,j); 
	for(int i=0;i<1<<cnt;i++) for(int j=0;j<=cnt;j++) dp[i][j]=0x3f3f3f3f;
	bfs(0,1,1);
	dp[0][0]=0;
	for(int i=0;i<1<<cnt;i++)
	{
		for(int j=0;j<=cnt;j++)
		{
			for(int l=1;l<=cnt;l++)
			{
				int p=i|(1<<(l-1));
				dp[p][l]=min(dp[p][l],dp[i][j]+dis[j][l]);
				if(dp[p][l]<=k) ans=max(ans,__builtin_popcount(p));
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}