吐槽
滚动

2017 C语言积分赛 周赛一 D题 末日时在做什么?有没有空?可以来编程吗? 题解

题目描述

在【黑玛瑙剑鬼】威廉·克梅修独战黑烛公之时,【极星大术师】史旺·坎德尔与【爆炸魔】艾米莎·霍铎温也正在前往讨伐翠钉侯的路上。但是,他们却遭遇了一个迷宫!

这是一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上,那么你可以移动到相邻4格中的某一格1上,同样若你位于一格1上,那么你可以移动到相邻4格中的某一格0上。

现在史旺想知道,对于给定的迷宫,询问从某一格开始能移动到多少个格子(包含自身)。请你帮他算一算,否则艾米莎就要开始不顾一切地爆破了!

输入

输入的第1行为两个正整数n,m。

下面n行,每行n个字符,字符只可能是0或者1,字符之间没有空格。

接下来m行,每行2个用空格分隔的正整数i,j,对应了迷宫中第i行第j列的一个格子,询问从这一格开始能移动到多少格。

数据规模与约定

对于100%的数据,n<=1000,m<=100000。

输出

输出包括m行,对于每个询问输出相应答案。

样例输入

样例输出

连通块问题,辅以并查集优化。

思路:

1、用fx[i][j]和fy[i][j]记录坐标为(i,j)的点所在连通块的特征点,uuu[i][j]记录坐标为(i,j)的点所在连通块的点个数。

2、先遍历图中所有点,对于没有特征点的点(x,y),进行dfs或bfs(本题解采用bfs),求得连通块后标记该连通块内所有点的特征点为(x,y),并使得uuu[x][y]等于该连通块里点的个数。

3、对于每个询问,先得到该点所在连通块的特征点,然后直接输出该特征点在uuu数组中的值。

Code:

 

Contents licensed under Creative Commons by-nc-sa 3.0.
Post Comment

Post Comment