C++

Forum

 
Fill 2-dimensional array with zeros, C++

ivyfisher (4)
There is a problem where I need to fill an array with zeros, with the following assumptions:

- in the array there can only be `0` and `1`
- we can only change `0` to `1` and `1` to `0`
- when we meet `1` in array, we have to change it to `0`, such that its neighbours are also changed, for instance, for the array like the one below:

1
2
3
 
     1 0 1
     1 1 1
     0 1 0


When we change element at (1,1), we then got the array like this:

1
2
3
 
     1 1 1
     0 0 0
     0 0 0


- We can't change the first row
- We can only change the elements that are in the array
- The final result is the number of times we have to change `1` to `0` to zero out the array

1) First example, array is like this one below:

1
2
3
 
     0 1 0
     1 1 1
     0 1 0


the answer is 1.

2) Second example, array is like this one below:

1
2
3
4
5
6
 
     0 1 0 0 0 0 0 0
     1 1 1 0 1 0 1 0
     0 0 1 1 0 1 1 1
     1 1 0 1 1 1 0 0
     1 0 1 1 1 0 1 0
     0 1 0 1 0 1 0 0


The answer is 10.

There also can be situations that its impossible to zero out the array, then the answer should be "impossible".

Somehow I can't get this working: for the first example, I got the right answer (1) but for the second example, program says `impossible` instead of 10.

Any ideas what's wrong in my code?

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
    #include <iostream>
    using namespace std;
    
    int main(int argc, char **argv)
    {
        int n,m;
    
        cin >> n >> m;
    
        bool tab[n][m];
    
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                cin >> tab[i][j];
                
        int counter = 0;
    
        for(int i=0; i<n-1; i++)
        {
            for(int j=0; j<m-1; j++)
            {
                if(tab[i][j] == 1 && i > 0 && j > 0)
                {
                    tab[i-1][j] = !tab[i-1][j];
    
                    tab[i+1][j] = !tab[i+1][j];
    
                    tab[i][j+1] = !tab[i][j+1];
    
                    tab[i][j-1] = !tab[i][j-1];
    
                    tab[i][j] = !tab[i][j];
    
                    counter ++;
                }
            }
        }
    
        bool impossible = 0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(tab[i][j] == 1)
                {
                    cout << "impossible\n";
                    impossible = 1;
                    break;
                }
            }
            if(impossible)
                break;
        }
    
        if(!impossible)
            cout << counter << "\n";
    
        return 0;
    }



Last edited on
whitenite1 (1785)
@ivyfisher

You can't create a 2d array at the start of your program, like that. I revamped your program so you can. Also added in prompts, etc. so you know what's to be expected. Width and height of array, inputting data, etc. Also showing the before and after data in the array.
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
// Lights.cpp : main project file.

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

int main()
{
	int i,n,m;

	do
	{
		cout << "How wide is the board? [ 3 to 10 ]"<<endl;
		cin >> m;
		if(m<3 || m > 10)
			cout << "Enter only 3 thru 10. Try again.." << endl;
	}while (m<3 || m > 10);

	do
	{
		cout << "And how many rows high? [ 3 to 10 ]"<< endl;
		cin >> n;
		if(n<3 || n > 10)
			cout << "Enter only 3 thru 10. Try again.." << endl;
	}while(n<3||n>10);
	// Create the 2d array at start-up
	bool** tab = new bool* [n];

	for (i = 0; i < n; i++)
	{
		tab[i] = new bool[m];
	}
	cout << "Let's fill in the array.." << endl;
	for(int i=0; i<n; i++)
	{
		cout << "Row #"<<i+1<<"..";
		for(int j=0; j<m; j++)
		{
			cin >> tab[i][j];
		}
	}

	int counter = 0;

	cout << "Board before.." << endl;
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			cout << " " << tab[i][j];
		}
		cout << endl;
	}

	for(int i=1; i<n-1; i++)
	{
		for(int j=1; j<m-1; j++)
		{
			if(tab[i][j] == 1)
			{
				tab[i-1][j] = !tab[i-1][j];

				tab[i+1][j] = !tab[i+1][j];

				tab[i][j+1] = !tab[i][j+1];
				
				tab[i][j-1] = !tab[i][j-1];

				tab[i][j] = !tab[i][j];

				counter ++;
			}
		}
	}

	cout << "Board after.." << endl;
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			cout << " " << tab[i][j];
		}
		cout << endl;
	}


	bool impossible = 0;
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			if(tab[i][j] == 1)
			{
				cout << "impossible" << endl;
				impossible = 1;
				break;
			}
		}
		if(impossible)
			break;
	}

	if(!impossible)
	{
		cout << endl << "Changed all to 0's in "<< counter << " moves." << endl;
	}
	cin >> n;// Just to keep console open
	return 0;
}


I think example 2 is flawed in changes.
-- Start --
1
2
3
4
5
6
 
1    0 1 0 0 0 0 0 0
2    1 1 1 0 1 0 1 0
3    0 0 1 1 0 1 1 1
4    1 1 0 1 1 1 0 0
5    1 0 1 1 1 0 1 0
6    0 1 0 1 0 1 0 0


Row 1, column 5, the 0 becomes a 1, and can never change back.
Same with row 1, column 7.

Well, you will be able to see the changes the way the program runs now.
ivyfisher (4)
I don't think you understood my question. My problem is not how to create a dynamic 2dimnesional array (btw, I created one correctly, but instead of dynamic, I have a ordinary array, which does not matter here. Also, you forgot to free allocated memory.)

I have the main problem with the correct algorithm which shoul full this array with zeros. I was thinking about backtracking solution maybe? But don't know how it should look.
Topic archived. No new replies allowed.