欢迎访问~原文出处——

---

---

题意概括

　　有一块矩形土地，被分为 N*M 块 1*1 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子A不可以走到格子B，就没有距离。 如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。 如果可以移走T块障碍物，求所有格子间的最大距离。 保证移走T块障碍物以后，至少有一个格子不含有障碍物。

　　n,m,t<=30

---

 

题解

　　格子很少。

　　所以我们选定起点，然后spfa求到达各个点的花费障碍数，这样可以判断是否可以到达这些点，然后根据这个直接暴力就可以了。

---

 

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=30+5,M=N*N;const int dx[4]={ 0, 0,-1, 1};const int dy[4]={-1, 1, 0, 0};int n,m,t,a[N][N];struct Queue{	int x,y;	void push(int x_,int y_){		x=x_,y=y_;	}	void pushout(int &x_,int &y_){		x_=x,y_=y;	}}q[M];int dis[N][N],qmod;bool f[N][N];bool check(int x,int y){	return 1<=x&&x<=n&&1<=y&&y<=n;}int sqr(int a){	return a*a;}int main(){	scanf("%d%d%d",&n,&m,&t);	for (int i=1,x;i<=n;i++){		char ch[N];		scanf("%s",ch+1);		for (int j=1;j<=m;j++)			a[i][j]=ch[j]-48;	}	int ans=0;	qmod=n*m+1;	for (int i=1;i<=n;i++)		for (int j=1;j<=m;j++){			memset(f,0,sizeof f);			memset(dis,63,sizeof dis);			int head=0,tail=0,x,y,x_,y_;			dis[i][j]=a[i][j];			f[i][j]=1;			q[tail=(tail+1)%qmod].push(i,j);			while (head!=tail){				q[head=(head+1)%qmod].pushout(x,y);				f[x][y]=0;				for (int i=0;i<4;i++){					x_=x+dx[i],y_=y+dy[i];					if (!check(x_,y_))						continue;					if (dis[x][y]+a[x_][y_]