题解 | #牛牛家的房子#

知识点:

1.模拟
2.枚举

基本思路:

遍历每一个房子
	1.如果没有人什么也不干
	2.反之,
    	试图让这个人移动,约束条件|x-x1|+|y-y1|<=r也就是x1的变化量+y1的变化量<=r
    	移动后判断有没有温度更高的点,有就保存
	直到没有让成功移动之后

代码实现:

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cfloat>
#include<set>
#include<unordered_map>
using namespace std;
int r, n, Temperature;;
pair<int, int> Move(vector<vector<pair<int, int>>>& home,int x,int y) {
    //记录移动到的新坐标
    pair<int, int> res = { x,y };
    int tem = home[x][y].first;
    // 移动的范围
    for (int xx = -r; xx <= r; xx++)
    {
        for (int yy = -r;yy <= r;yy++) {
            if (abs(yy) + abs(xx) <= r) {
                int newx = xx + x, newy = yy + y;
                //越界判断
                if (newx >= 0 && newx < n && newy < n && newy >= 0 && tem < home[newx][newy].first) {
                    //温度更高的房间
                    tem = home[newx][newy].first;
                    res.first = newx;
                    res.second = newy;
                }
            }
        }
    }
    return res;
}

void solve() {
    cin >> n >> r;
    //每一个房间的(温度,人数)
    vector<vector<pair<int, int>>> home(n,vector<pair<int,int>>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            cin >> Temperature;
            home[i][j] = { Temperature ,1};
        }

    //模拟(每一个房子的人移动)
    bool move = true;
    while (move) {
        move = false;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0;j < n;j++) {
                if (home[i][j].second != 0) {
                    pair<int, int> pos = Move(home, i, j);
                    int x = pos.first, y = pos.second;
                    if (x != i || y != j) {
                        //说明找到了更好的房子
                        move = true;
                        home[x][y].second += home[i][j].second;
                        home[i][j].second = 0;
                    }
                }
            }
        }
    }
    // a:表示有人的房子个数,b:同一间房子的最大人数
    int a = 0, b = home[0][0].second;
    int xx=0, yy = 0;   //假设(0,0)是最大人数的房子
    for (int i = 0; i < n; i++)
    {
        for (int j = 0;j < n;j++) {
            if (home[i][j].second != 0)    a++;
            if (home[i][j].second > home[xx][yy].second) {
                xx = i, yy = j, b = home[i][j].second;
            }
        }
    }

    cout << a << " " << b;
}


int main() {
    std::ios::sync_with_stdio(false); std::cin.tie(0);
    solve();
    return 0;
}