【滴滴笔试】第二道算法题哪里错了
用不相交集做的
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
//int ** land;
bool * has;
int m, n;
bool isIn(int r, int c, int m, int n) {
if(r >= 0 && r < m && c >= 0 && c < n) return true;
return false;
}
int find(int *adt, int x) {
if(adt[x] < 0) return x;
else return adt[x] = find(adt, adt[x]);
}
void ui(int * s, int root1, int t1, int t2) {
int root2 = t1 * n + t2;
if(!has[root2]) return;
root1 = find(s, root1);
root2 = find(s, root2);
if(root1 == root2) return;
s[root1] = root2;
}
int main()
{
int k;
cin>>m>>n>>k;
int** op = new int*[k];
for(int i = 0; i < k; i++) {
op[i] = new int[2];
}
int ret = 0;
for(int i = 0; i < k; i++) {
int r, c;
cin>>op[i][0]>>op[i][1];
}
int * adt = new int[m * n];
has = new bool[m * n];
for(int i = 0; i < m * n; i++) adt[i] = -1, has[i] = false;
for(int i = 0; i < k; i++) {
int r=op[i][0], c=op[i][1];
int l = r * n + c;
has[l] = true;
if(isIn(r - 1, c, m, n)) ui(adt, l, r - 1, c);
if(isIn(r + 1, c, m, n)) ui(adt, l, r + 1, c);
if(isIn(r, c - 1, m, n)) ui(adt, l, r, c - 1);
if(isIn(r, c + 1, m, n)) ui(adt, l, r, c + 1);
ret = 0;
for(int i = 0; i < m * n; i++)
if(adt[i] < 0 && has[i]) ret++;
cout<<ret;
if(i != k - 1) cout<<" ";
}
} 代码写的着急,看起来比较乱。
80%通过率。哪里错了?
