CodeForces 318D Ants

题目链接

题意:

有n仅仅蚂蚁和m次询问

n仅仅蚂蚁初始所有位于起点(0,0)处。每4仅仅蚂蚁在同一格就会以该格为中心向上下左右四个方向爬一格

一仅仅向上,一仅仅向下,一仅仅向左。一仅仅向右

假设每一个格子内的蚂蚁数量 < 4,那么蚂蚁就会停止运动

问你当全部的蚂蚁都停止运动后,给你随意的(x, y),输出该格子内的蚂蚁数量

思路:

模拟+暴力

由于询问x,y会有负的,所以最好还是设起始坐标为(N,N),由于起始位置的蚂蚁最多也就30000仅仅。所以N根本不是必需开到1e9那么大,事实上65就能够了,保险起见开了100,再大点预计要TLE;

当abs(x)和abs(y) > N的时候,超出范围,所以一定是0。

不停的遍历 (2*N)  * (2*N) 的格子,直到没有一个格子的蚂蚁数量>=4为止。

代码例如以下:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100;
typedef long long ll;
int n, t;
int map[2*N][2*N];
int main()
{
	scanf("%d%d", &n, &t);
	memset(map, 0, sizeof(map));
	int x = 0, y = 0;
	map[N][N] = n;
	bool flag = 1;
	while(flag)
	{
		flag = 0;
		for(x = 0; x < N*2; x++)
		{
			for(y = 0; y < N*2; y++)
			{
				if(map[x][y] >= 4)
				{
					flag = 1;
					int cnt = map[x][y] / 4;
					map[x-1][y] += cnt;
					map[x+1][y] += cnt;
					map[x][y-1] += cnt;
					map[x][y+1] += cnt;
					map[x][y] -= cnt * 4;
				}
			}
		}	
	}
	while(t--)
	{
		scanf("%d%d", &x, &y);
		printf("%d
", abs(x)<N && abs(y) < N ? map[N+x][N+y] : 0);
	}
} 

原文地址:https://www.cnblogs.com/slgkaifa/p/6871615.html