【滴滴笔试】第二道算法题哪里错了

用不相交集做的
#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%通过率。哪里错了?
#滴滴#
全部评论
这不是第一道吗
点赞 回复 分享
发布于 2017-09-23 22:40

相关推荐

10-28 14:42
门头沟学院 Java
watermelon1124:因为嵌入式炸了
点赞 评论 收藏
分享
totoroyyw:千年老妖😂
投递华为等公司10个岗位
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务