Little help in dynamic 2D Array

Maggi Iggam (123)
I was using a simple 2D array but its maximum limit was 1000*1000 but i required 3001*3001 array . Also Most of my array was empty but still that would require me to initialize it as 3001*3001 so i was thinking that solution could be that using only that much space that i would require , so can you pls tell me so using Dynamic Memory or any other alternate ???
My original code was this :-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include<cstdio>
#include <queue>
using namespace std;
int main() {
    //variable declarations
    int i,j,steps=1,n,m,s,t,tmp,tmp1,visited[10001];
    int buildings[1000][1000];
    queue<int> tovisit;
    //take inputs
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;i++) {
        scanf("%d %d",&tmp,&tmp1);
        buildings[tmp][buildings[tmp][0]+1]=tmp1;
        buildings[tmp][0]++;
        buildings[tmp1][buildings[tmp1][0]+1]=tmp;
        buildings[tmp1][0]++;
    }
    scanf("%d %d",&s,&t);
    if (s==t) {printf("0");goto gym;}
    //intialize queue tovisit
    visited[s]=1;
    for (i=1;i<=buildings[s][0];i++) {tovisit.push(buildings[s][i]);visited[buildings[s][i]]=1;}
    tovisit.push(-1);
    while (!tovisit.empty()) {
          if (tovisit.front()==t) {printf("%d",steps);break;}
          if (tovisit.front()==-1) {steps++;tovisit.pop();if (tovisit.empty()) {printf("0");break;}tovisit.push(-1);} else {
             for (i=1;i<=buildings[tovisit.front()][0];i++) {
if (visited[buildings[tovisit.front()][i]]!=1) {
for (j=1;j<=buildings[tovisit.front()][0];j++) if (visited[buildings[tovisit.front()][i]]!=1) tovisit.push(buildings[tovisit.front()][j]);
}
}
             visited[tovisit.front()]=1;
             tovisit.pop();
          }
    }
    gym:;
}
Last edited on
Moschops (7244)
Use vectors. They take care of their own memory.
Cubbi (4774)
Most of my array was empty but still that would require me to initialize it as 3001*3001 so i was thinking that solution could be that using only that much space that i would require


If by "empty" you mean "zero", you'd benefit from using a sparse matrix class, such as http://www.boost.org/doc/libs/release/libs/numeric/ublas/doc/matrix_sparse.htm
Last edited on
Maggi Iggam (123)
@Moschops , i tried replacing 2D array with 2D vectors , but still i am getting SIGABRT error after 3 test case . Could you tell me how to make my vector dynamic here :-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include<cstdio>
#include <queue>
#include <vector>
using namespace std;
int main() {
    //variable declarations
    int i,j,steps=1,n,m,s,t,tmp,tmp1,visited[1000001];
vector<vector<int> > buildings ( 3001, vector<int> ( 3001 ) );
    queue<int> tovisit;
    //take inputs
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;i++) {
        scanf("%d %d",&tmp,&tmp1);
        buildings[tmp][buildings[tmp][0]+1]=tmp1;
        buildings[tmp][0]++;
        buildings[tmp1][buildings[tmp1][0]+1]=tmp;
        buildings[tmp1][0]++;
    }
    scanf("%d %d",&s,&t);
    if (s==t) {printf("0");goto gym;}
    //intialize queue tovisit
    visited[s]=1;
    for (i=1;i<=buildings[s][0];i++) {tovisit.push(buildings[s][i]);visited[buildings[s][i]]=1;}
    tovisit.push(-1);
    while (!tovisit.empty()) {
          if (tovisit.front()==t) {printf("%d",steps);break;}
          if (tovisit.front()==-1) {steps++;tovisit.pop();if (tovisit.empty()) {printf("0");break;}tovisit.push(-1);} else {
             for (i=1;i<=buildings[tovisit.front()][0];i++) {if (visited[buildings[tovisit.front()][i]]!=1) {
for (j=1;j<=buildings[tovisit.front()][0];j++) if (visited[buildings[tovisit.front()][i]]!=1) tovisit.push(buildings[tovisit.front()][j]);
}
}
             visited[tovisit.front()]=1;
             tovisit.pop();
          }
    }
    gym:;
}


@Cubbi : Since i am giving programming olympiads , i have to work out solutions according to thier compiler which just has standard libraries and so i dont think we can use Boost libraries here
Last edited on
Topic archived. No new replies allowed.