首页 > 试题广场 >

车队管理

[编程题]车队管理
  • 热度指数：568 时间限制：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个位置。
算法知识视频讲解
添加回答
牛客277601090号头像 牛客277601090号
模拟+前缀和，数组大小参考大家的。看着别人答案都搞了好久🤐🤐🤐我是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)
牛客721590970号头像 牛客721590970号

应注意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)
chenfy2113头像 chenfy2113
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)
Java
pein531头像 pein531

模拟+二维前缀和

用最简单的思路去进行模拟，但是要探索一下测试数据究竟会给出多大的网格，最终测试得到结论：当从原点向四周延伸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)
C++
offer_plus_plus头像 offer_plus_plus
暴力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)
凌工路2号挖掘机小学附属大专西山7舍第一玛卡巴卡头像 凌工路2号挖掘机小学附属大专西山7舍第一玛卡巴卡
只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)
牛客459624837号头像 牛客459624837号 
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)
牛客922332741号头像 牛客922332741号
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)
叮叮sucess头像 叮叮sucess 
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)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 数据库工程师 信息技术岗 测试开发工程师 2019 大数据开发工程师 小马智行 数据分析师 Java工程师
上传者：小小
难度：
10条回答 6008浏览

热门推荐

通过挑战的用户

相关试题

车队管理

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号