首页 > 试题广场 >

车队管理

[编程题]车队管理
  • 热度指数:562 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小马智行(Pony.ai)在广州南沙区有一支稳定运营的自动驾驶车队,可以将南沙区的地图看做一个二维的网格图,小马智行的广州office在(0, 0)位置。
公司现在有n台车,每天会按如下规则从围绕南沙区进行路测:
1. 初始n辆车都在公司。
2. 放眼整个南沙地图,每过一分钟, 若有一个网格的车数大于等于8, 则这个网格同时会有8辆车分别前往上,下,左,右,左上,左下,右上,右下的网格,不停执行该步骤直到所有的车辆的位置都固定不变。
作为小马智行车辆控制中心的一员, 你需要监管车辆运营的情况, 你需要等到所有车辆的位置固定之后,进行q次抽样统计, 每次需要统计出以(x_1, y_1)为左下角,以(x_2, y_2)为右上角的矩形范围内车辆的车辆的数目。


输入描述:
第一行为n和q, 分别代表初始office内的车辆数和抽样的次数。
之后q行,每行包含4个变量x_1, y_1, x_2, y_2 含义见题目描述。
后, 进行q次抽样,每次查询以(x_1, y_1)为左下角,以(x_2, y_2)为右上角的矩形范围内车辆的数目。



输出描述:
输出q次抽样的结果,每次结果独占一行。
示例1

输入

8 2
0 0 0 0
-1 -1 1 1

输出

0
8

说明

第0分钟所有车辆都在office处。

第1分钟及以后, 8辆车分别在(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)这8个位置。
模拟+前缀和,数组大小参考大家的。看着别人答案都搞了好久🤐🤐🤐我是five
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> p;
int getfixed(int a,int c){
    int max=2*c;
    a+=c;
    if(a<=0) a=1;
    else if(a>max) a=max;
    return a;
}
int main(){
    int n,q;
    scanf("%d%d", &n,&q);
    vector<p> qs;
    for(int i=0;i<q;i++){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        qs.push_back(p(x1,y1));
        qs.push_back(p(x2,y2));
    }
    int center=100;//中心偏移量,估算最大数据得到
    int nums[2*center+1][2*center+1];
    memset(nums, 0, sizeof(nums));//初始化重要,否则超时
    nums[center][center]=n;
    int dx[8]={1,0,-1,1,0,-1,1,-1};
    int dy[8]={1,1,1,-1,-1,-1,0,0};
    bool done=false;
    while(!done){
        done=true;
        for(int i=0;i<2*center;i++)
            for(int j=0;j<2*center;j++){
                if(nums[i][j]>=8){
                    done=false;
                    //结果与移动速度无关,可以加快过程到剩下的<8辆
                    int step=nums[i][j]/8;
                    nums[i][j]%=8;
                    for(int k=0;k<8;k++){
                        int x=i+dx[k];
                        int y=j+dy[k];
                        if(x>=0&&y>=0) nums[x][y]+=step;
                    }
                }
            }
    }
    //前缀和,否则q(<100000)次求解会超时
    int sum[2*center+1][2*center+1];
    memset(sum, 0, sizeof(sum));//重要
    for(int i=0;i<2*center+1;i++)
        for(int j=0;j<2*center+1;j++){
            if(i==0&&j==0) sum[i][j]=nums[0][0];
            else if(i==0) sum[i][j]=sum[i][j-1]+nums[i][j];
            else if(j==0) sum[i][j]=sum[i-1][j]+nums[i][j];
            else sum[i][j]=sum[i-1][j]+sum[i][j-1]
                           -sum[i-1][j-1]+nums[i][j];
        }
    for(int i=0;i<=qs.size()-2;i+=2){
        //根据nums大小修剪矩形框,保证最小值为1,否则ans超出索引
        int xmin=getfixed(qs[i].first,center),
            xmax=getfixed(qs[i+1].first,center),
            ymin=getfixed(qs[i].second,center),
            ymax=getfixed(qs[i+1].second,center);
         //xmin,ymin减1,使矩形下边界位置也在求和之中
        long long ans=sum[xmax][ymax]+sum[xmin-1][ymin-1]
                      -sum[xmin-1][ymax]-sum[xmax][ymin-1];
         
        cout<<ans<<endl;
    }
}


发表于 2022-08-01 20:31:10 回复(0)

应注意n大小,最后有车格子组成的图形大小是有限的且是正方形。根据对称性,先算1/8小块的车流量,然后再映射到大的地图上。

#include
#include
using namespace std;
const int ms = 128;
void print1(int m[ms][ms], int s = 8) {
    for(int i=-s; i<=s; i++) {
        for(int j=-s; j<=s; j++)
            if(abs(i)<=abs(j)) cout << m[abs(i)][abs(j)] << ' ';
            else cout << m[abs(j)][abs(i)] << ' ';
        cout << endl;
    }
    cout << "----------------" << endl;
}
void print2(int m[ms*2][ms*2], int s = 8) {
    for(int i=ms-s; i<=ms+s; i++) {
        for(int j=ms-s; j<=ms+s; j++)
            cout << m[i][j] << ' ';
        cout << endl;
    }
    cout << "----------------" << endl;
}
void weight(int bff[ms][ms], int x, int y, int f = 0) {
    if(x y) return;
    if(x==0 && y==0) bff[x][y] += 4;
    else if(x==0 && !(f==1)) bff[x][y] += 2;
    else if(x==y && !(f==2)) bff[x][y] += 2;
    else bff[x][y] += 1;
}
void trans(int bff[ms][ms], int x, int y) {
    if(x==0 && y==1) bff[x][y] -= 6;
    else if(y-x==1) bff[x][y] -= 7;
    else bff[x][y] -= 8;
    weight(bff, x-1, y-1, x==y?2:0);
    weight(bff, x-1, y);
    weight(bff, x-1, y+1);
    weight(bff, x, y-1, x==0?1:0);
    weight(bff, x, y+1, x==0?1:0);
    weight(bff, x+1, y-1);
    weight(bff, x+1, y);
    weight(bff, x+1, y+1, x==y?2:0);
}
void update(int m[ms][ms], bool & noUpdate) {
    static int s = 1;
    int bff[ms][ms];
    noUpdate = true;
    memset(bff, 0, sizeof(bff));
    if(m[0][0]>=8) {
        noUpdate = false;
        bff[0][0] -= 8; bff[0][1] ++;
        bff[1][1] ++;
    }
    for(int i=0; i < s; i++)
        for(int j=i; j < s; j++)
        if(m[i][j]>=8 && !(i==0 && j==0)) {
            noUpdate = false;
            trans(bff, i, j);
        }
    if(bff[0][s]>0) s++;
    for(int i=0; i< s; i++)
        for(int j=i; j < s; j++)
        m[i][j] += bff[i][j];
}
const int c = 100;
void dev(int & x, int offset = 0) {
    x += offset;
    if(x>c) x = c;
    else if(x<-c) x = -c;
    x += ms;
}
int main() {
    int m[ms][ms];
    int n, q;
    memset(m, 0, sizeof(m));
    cin >> n >> q;
    bool noUpdate = false;
    m[0][0] = n;
    while(!noUpdate) update(m, noUpdate);
    int mm[ms*2][ms*2];
    int sum[ms*2][ms*2];
    memset(mm, 0, sizeof(mm));
    memset(sum, 0, sizeof(sum));
    for(int i=0; i<= c; i++)
        for(int j=i; j <= c; j++) {
            mm[ms+i][ms+j] = m[i][j];
            mm[ms+i][ms-j] = m[i][j];
            mm[ms-i][ms+j] = m[i][j];
            mm[ms-i][ms-j] = m[i][j];
            mm[ms+j][ms+i] = m[i][j];
            mm[ms+j][ms-i] = m[i][j];
            mm[ms-j][ms+i] = m[i][j];
            mm[ms-j][ms-i] = m[i][j];
        }
    for(int i=ms-c; i<= ms+c; i++)
        for(int j=ms-c; j <= ms+c; j++) {
            sum[i][j] = mm[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
        }
    //print2(mm);
    //print2(sum);
    while(q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        dev(x1,-1); dev(y1,-1); dev(x2); dev(y2);
        //cout << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
        //cout << " " << sum[x1][y1] << " " << sum[x2][y2] << " " << sum[x1][y2] << " " << sum[x2][y1] << endl;
        cout << sum[x1][y1] - sum[x1][y2] - sum[x2][y1] + sum[x2][y2] << endl;
    }
}
发表于 2020-11-09 23:47:43 回复(0)
70%
import sys

lines = sys.stdin.readlines()

num_all, query_all = lines[0].strip().split()
num_all = int(num_all)
query_all = int(query_all)

DICT_ALL = {0: {0: int(num_all)}}

def add_num_to_dict_all(temp_x, temp_y):
    x_lowwer = temp_x - 1
    y_lowwer = temp_y - 1
    x_upper = temp_x + 1
    y_upper = temp_y + 1
    for x in [x_lowwer, temp_x, x_upper]:
        if x not in DICT_ALL:
            DICT_ALL[x] = {}
        for y in [y_lowwer, temp_y, y_upper]:
            if x == temp_x and y == temp_y:
                continue
            if y not in DICT_ALL[x]:
                DICT_ALL[x][y] = 1
            else:
                DICT_ALL[x][y] += 1
                if DICT_ALL[x][y] >= 8:
                    BIG_LIST.append((x, y))

BIG_LIST = [(0, 0)]

while BIG_LIST:
    for x, y in BIG_LIST.copy():
        if DICT_ALL[x][y] >= 8:
            add_num_to_dict_all(x, y)
            DICT_ALL[x][y] -= 8
            if DICT_ALL[x][y] < 8:
                BIG_LIST.remove((x, y))
        else:
            BIG_LIST.remove((x, y))

query_all = [list(map(int, line.strip().split())) for line in lines[1:] if line.strip()]
for item in query_all:
    sum = 0
    for x_key, x_value in DICT_ALL.items():
        if item[0] <= x_key <= item[2]:
            for y_key, y_value in x_value.items():
                if item[1] <= y_key <= item[3]:
                    sum += DICT_ALL[x_key][y_key]
    print(sum)

超时了

发表于 2020-08-07 15:45:04 回复(1)
解题思路:
·如果只考虑往外扩张的车辆,发现只能扩展log层,猜想车辆的活动半径不会很大,打表发现是个类似圆形的图形,也就说明车辆的移动直径是根号n级别的,把横纵坐标都+500,可以直接用数组来模拟
·会发现车辆的移动顺序是无关的,假如一个方格内有16辆车,一次移动8辆和一次移动16辆是等价的,模拟的时候就可以把尽可能多的车移动出去。

#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define Please return
#define AC 0
using namespace std;
template <class T>
void read(T &val) { T x = 0; T bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }

int n,m;
queue<pii>qq[2];
int mp[1100][1100],nw;
void move(){
    while(!qq[nw].empty()){
        auto tp = qq[nw].front();qq[nw].pop();
        if(mp[tp.first][tp.second]<8) continue;
        int add = mp[tp.first][tp.second]/8;
        fo(i,-1,1){
            fo(j,-1,1){
                if(i==0&&j==0) continue;
                mp[tp.first+i][tp.second+j]+=add;
                if(mp[tp.first+i][tp.second+j]>=8) qq[nw^1].push({tp.first+i,tp.second+j});
            }
        }
        mp[tp.first][tp.second]%=8;
    }
    nw^=1;
}

int sum[1100][1100];
void change(int &x){//打表发现,半径不超过100
    x = min(x,100);x = max(x,-100);
    x+=500;
}
int main(){
    read(n);read(m);
    if(n>=8) qq[0].push({500,500});
    mp[500][500] = n;
    while(!qq[nw].empty()){
        move();
    }
    fo(i,1,1000){
        fo(j,1,1000){
            sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mp[i][j];
        }
    }
    while(m--){
        int x1,y1,x2,y2;read(x1);read(y1);read(x2);read(y2);
        change(x1);change(y1);change(x2);change(y2);
        printf("%d\n",sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]);
    }
    Please AC;
}


编辑于 2021-01-27 21:20:54 回复(0)

模拟+二维前缀和

用最简单的思路去进行模拟,但是要探索一下测试数据究竟会给出多大的网格,最终测试得到结论:当从原点向四周延伸100的距离时能够覆盖测试数据的极限。感觉如果是笔试场合不给出bad case的话基本是做不出来的。
import java.io.*;
import java.util.*;

public class Main {
    private static int[] dx = {-1, 1, 0, 0, -1, 1, -1, 1};
    private static int[] dy = {0, 0, -1, 1, -1, 1, 1, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int q = Integer.parseInt(params[1]);
        int offset = 100, N = (offset << 1)|1;
        int[][] grid = new int[N][N];
        grid[offset][offset] = n;
        boolean change = true;
        while(change){
            change = false;
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    if(grid[i][j] >= 8){
                        change = true;
                        // 若干波8辆车分散到8个方向
                        for(int k = 0; k < 8; k++){
                            int x = i + dx[k];
                            int y = j + dy[k];
                            if((0 <= x && x < N) && (0 <= y && y < N)){
                                grid[x][y] += grid[i][j] / 8;
                            }
                        }
                        grid[i][j] %= 8;
                    }
                }
            }
        }
        // 矩阵前缀和
        int[][] prevSum = new int[N][N];
        for(int x = 0; x < N; x++) {
            for(int y = 0; y < N; y++) {
                if(x == 0 && y == 0) {
                    prevSum[x][y] = grid[x][y];
                }else if(x == 0) {
                    prevSum[x][y] = grid[x][y] + prevSum[x][y - 1];
                }else if(y == 0) {
                    prevSum[x][y] = grid[x][y] + prevSum[x - 1][y];
                }else{
                    prevSum[x][y] = grid[x][y] + prevSum[x - 1][y] + prevSum[x][y - 1] - prevSum[x - 1][y - 1];
                }
            }
        }
        // 查询
        while(q-- > 0){
            params = br.readLine().split(" ");
            int x1 = Integer.parseInt(params[0]);
            int y1 = Integer.parseInt(params[1]);
            int x2 = Integer.parseInt(params[2]);
            int y2 = Integer.parseInt(params[3]);
            // 卡边界
            x1 = Math.max(offset + x1, 1);
            y1 = Math.max(offset + y1, 1);
            x2 = Math.min(offset + x2, N - 1);
            y2 = Math.min(offset + y2, N - 1);
            if(x1 > x2 || y1 > y2){
                System.out.println(0);
            }else{
                System.out.println(prevSum[x2][y2] - prevSum[x1 - 1][y2] - prevSum[x2][y1 - 1] + prevSum[x1 - 1][y1 - 1]);
            }
        }
    }
}

编辑于 2022-04-18 16:51:07 回复(0)
暴力bfs去算一下小车数10000时,最终的最大上下左右边界,发现不超过80, 然后就用偏移量将坐标搞一搞,然后查询的坐标也搞一搞,然后前缀和求一下就过了
#include <bits/stdc++.h>
using namespace std;

/************************<head>*************************/
#define fi first
#define se second
#define ios() cin.tie(nullptr)->sync_with_stdio(false)
typedef pair<int, int> pii;

/*********************<begin code>**********************/
const int M = 210, BASE = 100; // 范围在[-76, +76]
int cnt[M][M];
bool st[M][M];
const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

void bfs(int n) {
	queue<pii> q;
	q.push({BASE, BASE});
	cnt[BASE][BASE] = n;
	st[BASE][BASE] = true;
	while (q.size()) {
		auto p = q.front(); q.pop();
		int x = p.fi, y = p.se;
		st[x][y] = false;
		int &t = cnt[x][y];
		if (t < 8) continue;
		int add = t / 8;
		t %= 8;
		for (int i = 0; i < 8; ++i) {
			int x0 = x + dx[i];
			int y0 = y + dy[i];
			cnt[x0][y0] += add;
			if (!st[x0][y0] && cnt[x0][y0] >= 8) {
				st[x0][y0] = true;
				q.push({x0, y0});
			}
		}
	}
}

void solve() {
	int n, m;
	cin >> n >> m;

	bfs(n); // 模拟一下
	for (int i = 1; i < M; ++i)  // 算一下前缀和
		for (int j = 1; j < M; ++j)
			cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];

	for (int i = 0; i < m; ++i) {
		int x0, y0, x1, y1;
		cin >> x0 >> y0 >> x1 >> y1;
		x0 += BASE; y0 += BASE;
		x1 += BASE; y1 += BASE;
		x0 = max(1, min(200, x0));  // 1~200之间
		y0 = max(1, min(200, y0));  // 1~200之间
		x1 = max(1, min(200, x1));  // 1~200之间
		y1 = max(1, min(200, y1));  // 1~200之间
		cout << cnt[x1][y1] - cnt[x0 - 1][y1] - cnt[x1][y0 - 1] + cnt[x0 - 1][y0 - 1] << '\n';
	}
}

int main() {
	ios();
	solve();
	return 0;
}


发表于 2023-01-13 17:09:42 回复(0)
只guole40%...感觉挺简单的啊... 用 ‘x,y’作为字典的key,value为节点处的车辆数,每次循环时范围拓展一圈(init函数);用stack记录每轮车辆大于8的节点,将这些节点扩散(depart函数)如果stack空了那么就不能移动了,至此move函数结束。然后遍历所有节点找到
n,Q = list(map(int, input().split()))
 
dic = {}
dic['0,0'] = n
 
def move(): #模拟扩散过程
    stack = [] # 记录本轮会出车的节点
    if n >= 8:
        stack.append('0,0')
    k = 0
    while stack:
        init(k) #记录的范围扩大一圈
        tempstack = []
        while stack:
            # print(stack)
            node = stack.pop()
            i,j = list(map(int,node.split(',')))
            tempstack += depart(i,j)
        stack = tempstack  #新一轮会出车的节点
        # print(stack)
        k +=1
    return k

def init(k): 
    dic['{},{}'.format(k + 1, k + 1)] = 0
    dic['{},{}'.format(k + 1, -k - 1)] = 0
    dic['{},{}'.format(-k - 1, k + 1)] = 0
    dic['{},{}'.format(-k - 1, -k - 1)] = 0
    for i in range(-k,k+1):
        dic['{},{}'.format(i, k + 1)] = 0
        dic['{},{}'.format(i, -k - 1)] = 0
        dic['{},{}'.format(k + 1, i)] = 0
        dic['{},{}'.format(-k - 1, i)] = 0

def depart(i,j): #记录了所有大于8的节点,其中有重复,用dic['{},{}'.format(i,j)]>=8判断
    ans = []
    if dic['{},{}'.format(i,j)]>=8:
        dic['{},{}'.format(i,j)] -= 9
        for d1 in range(-1,2):
            for d2 in range(-1,2):
                dic['{},{}'.format(i + d1,j + d2)] += 1
                if dic['{},{}'.format(i + d1,j + d2)] >= 8:
                    ans.append('{},{}'.format(i + d1,j + d2))
    return ans

k = move()
# print(dic)
for q in range(Q):
    x1,y1,x2,y2 = list(map(int, input().split()))
    x1 = min(x1,k) if x1>0 else max(x1,-k)
    x2 = min(x2, k) if x2 > 0 else max(x2, -k)
    y1 = min(y1, k) if y1 > 0 else max(y1, -k)
    y2 = min(y2, k) if y2 > 0 else max(y2, -k)

    count = 0
    for x in range(x1,x2+1):
        for y in range(y1,y2+1):
            count += dic['{},{}'.format(x,y)]
    print(count)


发表于 2022-09-17 14:56:15 回复(0)
n, q = [int(i) for i in input().split(" ")]
moving = 1 if n > 8 else 0
l = n
carMap = [[0]*(2*l+1) for _ in range(2*l+1)]
carMap[l][l] = n
while moving:
    moving = 0
    carMove = [[0]*(2*l+1) for _ in range(2*l+1)]
    for i in range(2*l+1):
        for j in range(2*l+1):
            if carMap[i][j] > 8:
                moving = 1
                for p in [-1,0,1]:
                    for qi in [-1,0,1]:
                        carMove[i+p][j+qi] += 1
                carMove[i][j] -= 9
    if moving:
        for i in range(2*l+1):
            for j in range(2*l+1):
                carMap[i][j] += carMove[i][j]


for k in range(q):
    x1,y1,x2,y2 = [int(i) for i in input().split(" ")]
    x1 = min(max(x1,-l),l)
    y1 = min(max(y1,-l),l)
    x2 = min(max(x2,-l),l)
    y2 = min(max(y2,-l),l)
    print(sum(list(map(sum, [i[l+x1:l+x2+1] for i in carMap[l+y1:l+y2+1]]))))
    # print(sum(carMap[l+y1:l+y2+1][l+x1:l+x2+1]))
30% 通过 其余超时
发表于 2020-12-09 22:00:35 回复(0)
60% 超时了
from collections import Counter
from sys import stdin
 
first_line = stdin.readline().strip()
N, Q = list(map(int, first_line.split(" ")))
 
car_list = [[0, 0] for _ in range(N)]
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
 
 
def positionlist2move(car_list):
    counter = Counter([tuple(x) for x in car_list])
    return [x[0] for x in counter.most_common() if x[1] >= 8]
 
 
def movecar_batch(cars):
    assert len(cars) == 8, len(cars)
    for car, d in zip(cars, directions):
        car[0] += d[0]
        car[1] += d[1]
 
 
while True:
    positions2move = positionlist2move(car_list)
    if len(positions2move) == 0:
        break
    for position in positions2move:
        cars = [x for x in car_list if x == list(position)][:8]
        movecar_batch(cars)
 
for _ in range(Q):
    x1, y1, x2, y2 = list(map(int, stdin.readline().strip().split(" ")))
    avaible_cars = [x for x in car_list if x1 <= x[0] <= x2 and y1 <= x[1] <= y2]
    print(len(avaible_cars))

发表于 2020-12-03 17:32:15 回复(0)
def descri_car(n, intial_loc, dict):

    if n < 8:
        dict[tuple(intial_loc)] = n
        return
    else:
        every_num = n // 8
        sur = list()
        sur.append([intial_loc[0] + 0,intial_loc[1] + 1])
        sur.append([intial_loc[0] + 0,intial_loc[1] + -1])
        sur.append([intial_loc[0] + 1,intial_loc[1] + 0])
        sur.append([intial_loc[0] + -1,intial_loc[1] + 0])
        sur.append([intial_loc[0] + 1,intial_loc[1] + -1])
        sur.append([intial_loc[0] + -1,intial_loc[1] + 1])
        sur.append([intial_loc[0] + 1,intial_loc[1] + 1])
        sur.append([intial_loc[0] + -1,intial_loc[1] + -1])
        dict[tuple(intial_loc)] = n
        for i in range(8):
            if not dict.get(tuple(sur[i])):
                dict[tuple(sur[i])] = every_num
                dict[tuple(intial_loc)] = dict[tuple(intial_loc)] - every_num
            else:
                dict[tuple(sur[i])] += every_num
                dict[tuple(intial_loc)] = dict[tuple(intial_loc)] - every_num
        temp_dic = {}
        for i in dict.keys():
            if dict[i] >= 8:
                temp_dic[i] = dict[i]
                # print(temp)
        for i in temp_dic.keys():
            temp = dict[i]
            descri_car(temp, i, dict)

def car_number(loc, dict):
    x1,y1,x2,y2 = loc[0], loc[1], loc[2], loc[3]
    key = list(dict.keys())
    sum = 0
    for i in key:
        if i[0] >= x1 and i[0] <= x2 and i[1] >= y1 and i[1] <= y2:
            sum += dict[i]
    return sum


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    i = 0
    ins_sym = list()
    # 每个元素是一个列表,具有4个元素,分别是两组坐标
    while i < m:
        data = list(map(int, input().split()))
        ins_sym.append(data)
        i += 1
    # 两个函数,一个分配位置,一个计算数目
    intial_loc = [0, 0]
    dict = {}
    descri_car(n, intial_loc, dict)
    for i in ins_sym:
        print(car_number(i, dict))

发表于 2020-07-23 18:20:31 回复(0)