Sample Input 1 Sample Output 1
4 6 5 2 2 2 6 1 3 4 3 2 5 3 5 4 6 4 6 1 6 4 6 1 3 3 4 3 这题输出方式让我想死。。。之前训练比赛时认为是输入一行就输出一行。。结果一直output limit exceeded。。后面看了别人的才发现是输完后再一起输出。。想死的心都有了。 思路:从最后一张图开始往前推,再用并查集解决。详细看代码 #include<stdio.h> #include<string.h> #define MAXN 1010 struct stock{ int x1, x2, y1, y2; }pos[10010]; int num[MAXN*MAXN], fa[MAXN*MAXN],ans[10010];//num表示当前位置涂了几个黑点 ans[n]表示第n次画横线时白色连通块的个数 int dir[4][2] = { 0, 1, -1, 0, 0, -1, 1, 0 }; int m, n, p,t; int hash(int x, int y)//用哈希表表示 { int num = (x - 1)*m + y; return num; } void init()//初始化 { for (int i = 1; i <= n*m; i++) { fa[i] = i; num[i] = 0; } } int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void merge(int x, int y)//将两个相邻连通块连接在一起 { int fx = find(x), fy = find(y); if (fx == fy) return; t--;//t表示连通块个数 fa[fx] = fy; } bool check(int x, int y) { if (x >= 1 && y >= 1 && x <= n&&y <= m) return true; return false; } void work(int x,int y)//将刚出现的白块连到连通块中 { for (int i = 0; i < 4; i++) { int xx = x + dir[i][0]; int yy = y + dir[i][1]; if (check(xx, yy) && !num[hash(xx,yy)]) { merge(hash(xx,yy), hash(x,y)); } } } int main() { scanf("%d %d %d", &n, &m, &p); t = m*n; init(); //画黑线 for (int i = 1; i <= p;i++) { scanf("%d%d%d%d", &pos[i].x1, &pos[i].y1, &pos[i].x2, &pos[i].y2); for (int x = pos[i].x1; x <= pos[i].x2; x++) { for (int y = pos[i].y1; y <= pos[i].y2; y++) { if (num[hash(x, y)] == 0) t--; num[hash(x, y)]++; } } } //求出最后一个图的白色连通块的个数 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (!num[hash(i,j)]) { work(i, j); } } } //向前面的图推 for (int i = p; i > 0; i--) { ans[i] = t; //一步一步撤去黑线 for (int x = pos[i].x1; x <= pos[i].x2; x++) { for (int y = pos[i].y1; y <= pos[i].y2; y++) { num[hash(x, y)]--; if (num[hash(x, y)] == 0) { t++;//黑块撤完白块数目增加 work(x, y); } } } } for (int i = 1; i <= p; i++) { printf("%d\n", ans[i]); } return 0; }在比赛时从正面进行时是通过黑块入手的,发现时间没有超,但一直 output limit exceeded