个人网站托管,庭院设计效果图,电脑培训班零基础,什么是网络营销成败的关键一、题目大意
在(0xw#xff0c;0yh)的坐标系里有多个矩形#xff0c;把区域分成了多个部分#xff0c;我们需要针对找出被矩形分割的连通的区块数量。
二、解题思路
这个题目其实和学DFS时候那个找出连通的水洼是一样的。只是这个地图比较大#xff0c…一、题目大意
在(0xw0yh)的坐标系里有多个矩形把区域分成了多个部分我们需要针对找出被矩形分割的连通的区块数量。
二、解题思路
这个题目其实和学DFS时候那个找出连通的水洼是一样的。只是这个地图比较大没办法建立那么大的数组但是矩形的数量也很少所以考虑使用坐标离散化。
坐标离散化的思路其实也很简单就是我们把每一个有效坐标k和它 的前一个k-1和后一个坐标k1都放在一个数组里然后对这个数组排序加去重先排序再双指针去重最快之后用元素k在这个数组里的位置来替换这个元素本身的值这种离散化对于需要打表的题比如DP、DFS、BFS比较有效。
本题目给出的是坐标但是DFS需要用的是区块所以我就把(x1,y1)到(x2,y2)的矩形看作从[x1,x2-1]到[y1,y2-1]这些坐标中间的区块。那么[0,w-1]的坐标范围其实真正的放置区块的数量就是[0,w-2]也就是w-1个区块这个说的其实不清晰我表达能力确实是太差了。主要的意思就是解释下为什么我把去重后的数量-1作为w和h因为坐标和区块之间差一个所以减少一个。
三、代码
#include iostream
#include algorithm
#include queue
using namespace std;
typedef pairint, int P;
int x[6007], y[6007], xLen, yLen, w, h, x_1[1007], x_2[1007], y_1[1007], y_2[1007], n, ans;
int dx[] {1, 0, -1, 0}, dy[] {0, 1, 0, -1};
bool field[6007][6007];
queueP que;
void input()
{ans 0;scanf(%d, n);for (int i 0; i n; i){scanf(%d%d%d%d, x_1[i], y_1[i], x_2[i], y_2[i]);}
}
void compress()
{xLen 0;for (int i 0; i n; i){if (x_1[i] 0){x[xLen] x_1[i] - 1;}x[xLen] x_1[i];if (x_1[i] w){x[xLen] x_1[i] 1;}if (x_2[i] 0){x[xLen] x_2[i] - 1;}x[xLen] x_2[i];if (x_2[i] w){x[xLen] x_2[i] 1;}}yLen 0;for (int i 0; i n; i){if (y_1[i] 0){y[yLen] y_1[i] - 1;}y[yLen] y_1[i];if (y_1[i] h){y[yLen] y_1[i] 1;}if (y_2[i] 0){y[yLen] y_2[i] - 1;}y[yLen] y_2[i];if (y_2[i] h){y[yLen] y_2[i] 1;}}sort(x, x xLen);sort(y, y yLen);
}
void distinctBy2Posinter()
{int tmpLen 1;for (int i 1; i xLen; i){if (x[tmpLen - 1] ! x[i]){x[tmpLen] x[i];}}xLen tmpLen;tmpLen 1;for (int i 1; i yLen; i){if (y[tmpLen - 1] ! y[i]){y[tmpLen] y[i];}}yLen tmpLen;
}
void handleX_1X_2Y_1Y_2()
{for (int i 0; i n; i){x_1[i] lower_bound(x, x xLen, x_1[i]) - x;x_2[i] lower_bound(x, x xLen, x_2[i]) - x;y_1[i] lower_bound(y, y yLen, y_1[i]) - y;y_2[i] lower_bound(y, y yLen, y_2[i]) - y;}w xLen - 1;h yLen - 1;
}
void handleField()
{for (int i 0; i h; i){for (int j 0; j w; j){field[i][j] true;}}for (int i 0; i n; i){for (int j y_1[i]; j (y_2[i] - 1); j){for (int k x_1[i]; k (x_2[i] - 1); k){field[j][k] false;}}}
}
void bfs()
{while (!que.empty()){P p que.front();que.pop();for (int i 0; i 4; i){int ny p.first dy[i];int nx p.second dx[i];if (ny 0 ny h nx 0 nx w field[ny][nx]){field[ny][nx] false;que.push(P(ny, nx));}}}
}
void solve()
{for (int i 0; i h; i){for (int j 0; j w; j){if (field[i][j]){field[i][j] false;que.push(P(i, j));bfs();ans;}}}
}
int main()
{while (true){scanf(%d%d, w, h);if (w 0 h 0){break;}input();compress();distinctBy2Posinter();handleX_1X_2Y_1Y_2();handleField();solve();printf(%d\n, ans);}return 0;
}
