思路:对一个点每次移动的终点仅有温度和距离这里个定值决定,所以每一轮中一个位置的移动终点是固定的,确定移动终点之后,在循环中反复移动直至无法移动(可以移动点的人数为0)即可
个人难点:一开始的时候对于移动终点的判断不知道怎么去实现,因为对于一个点的x-r或者y-r等等可能是数组越界的,看了一些大佬的提交后,才知道可以对于一个点可以直接枚举所有其他点,判断是否为终点。
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int n,r;
cin>>n>>r;
int tem[21][21];//储存温度值
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>tem[i][j];
int num[21][21];//储存点的人数
int x[21][21][2]={0};//存储每个点移动一次时的移动终点
/*寻找每个点的移动终点(移动一次)*/
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
num[i][j]=1;
int max_x=i,max_y=j;
for(int k=0;k<n;k++)
for(int l=0;l<n;l++)
{
if(tem[k][l]>tem[max_x][max_y]&&abs(i-k)+abs(j-l)<=r&&(i!=k||l!=j))
{
max_x=k;
max_y=l;
}
}
if(max_x==i&&max_y==j)
{
x[i][j][0]=-1;
x[i][j][1]=-1;
}//如果是本身的话说明不移动
else
{
x[i][j][0]=max_x;
x[i][j][1]=max_y;
}
}
}
int max_num=0;
/*在循环中反复*/
while(1)
{
int not_empty=0;//记录一轮非空点数
int move_num=0;//记录一轮中可以移动的点数
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(num[i][j]>0&&x[i][j][0]!=-1)//如果人数非空且可以移动就移动
{
num[x[i][j][0]][x[i][j][1]]+=num[i][j];
num[i][j]=0;
move_num++;
}
}
/*遍历最终结果找最大人数*/
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(max_num<num[i][j])
max_num=num[i][j];
if(num[i][j]>0)
not_empty++;
}
}
/*打印结果*/
if(!move_num)
{
cout<<not_empty<<" "<<max_num;
break;
}
}
return 0;
}