CareerCup

Actually you should use UnionFind datastructure (algs4.cs.princeton.edu/15uf/)

// r is temporary array to store the elements of each group.
int f(int a[7][5], int r[7][5])
{
    const int m = 7;
    const int n = 5;
    int c = 0;
    memset(r, 0, sizeof(int)*m*n);
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            int x1 = i, y1 = j;
            if (a[x1][y1] != -1) {
                continue;
            }
            if (x1+1 < m && a[x1+1][y1] == -1) {
                if (r[x1][y1] == 0) {
                    r[x1][y1] = ++c;
                }
                r[x1+1][y1] = r[x1][y1];
            }
            if (y1+1 < n && a[x1][y1+1] == -1) {
                if (r[x1][y1] == 0) {
                    r[x1][y1] = ++c;
                }
                r[x1][y1+1] = r[x1][y1];
            }
        }
    }
    return c;
}

I didn't get the question

I understand the question as this - you can move left, right, top or bottom from any cell that has -1 in it. The cell you are moving to should also be -1 to qualify as connected. I would use an approach similar to BFS.

1. Have a boolean Visited Matrix of the same size as the original matrix.
2. Push the first cell with -1 into a queue. - syay queue1
3. dequeue a cell and push it into another queue q2 and mark the corresponding visited Matrix cell to true.
4. Get the adjacent cells (with a helper function) of the dequeued cell with -1 in it.
5. Push the adjacent cells into the queue1.
Repeat 3 thru 5 until no more cells are in the queue1

Now repeat from step 2 until you have visited all cells.

class Solution {

	// the method to call
	public int numConnected(int[][] mat) {
		int w = mat[0].length;
		int h = mat.length;
		int[][] visited = new int[h][w];
		int sum = 0;

		// init visited matrix
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++)
				visited[i][j] = 0;
		}
		/*	For each point, flood it;
			If it is a new connected component, then skip;
			Otherwise, count++;
		*/
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				sum += flood(i, j, mat, visited);
			}
		}

		return sum;
	}

	private int flood(int x, int y, int[][] mat, int[][] visited) {
		if (visited[x][y] == 1)
			return 0;

		if (mat[x][y] == -1) {
			visited[x][y] = 1;
			flood(x+1, y, mat, visited);
			flood(x, y+1, mat, visited);
			flood(x-1, y, mat, visited);
			flood(x, y-1, mat, visited);
			return 1;
		}

		return 0;
	}
}

#include <iostream>
#include <conio.h>
using namespace std;

int map[9][7] = {
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0,-1, 0,-1, 0, 0, 0 },
    { 0,-1,-1, 0,-1,-1, 0 },
    { 0, 0, 0, 0, 0,-1, 0 },
    { 0, 0, 0, 0,-1,-1, 0 },
    { 0, 0, 0, 0,-1, 0, 0 },
    { 0, 0,-1, 0, 0, 0, 0 },
    { 0, 0,-1, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0 },
  };

int temp[9][7] = {
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0 },
  };

int cnt = 0;

void check_connected(int i, int j, int flag) {
    if((i >= 0 ) && (i < 9) && (j >= 0) && (j < 7)) {
      if(map[i][j] == -1 && temp[i][j] == 0) {
        if(flag == 0) {
          cnt++;
          flag = 1;
        }
        temp[i][j] = 1;
        printf("(%d,%d)\n", i, j);
        check_connected(i+1,j,flag);
        check_connected(i,j+1,flag);
        check_connected(i-1,j,flag);
        check_connected(i,j-1,flag);
      }             
    }
}

int main() {
  for(int i = 0; i < 9; i++) {
    for(int j = 0; j < 7; j++) {
      if(map[i][j] == -1 && temp[i][j] == 0) {
        check_connected(i,j,0);     
        printf("\n");
      }      
    }        
  }   
  cout<<cnt;  
  getch();  
  return 0; 
}

This is O(num_row*num_col) solution and also changes the matrix, so if the matrix is later required then its copy is needed.
For each cell (i,j) in the matrix do the following:

if (a[i][j] == -1) Call find(i,j), count++;

find(i,j) works somewhat like this:
1. for r = i-1, c = j; r = i+1, c= j; r =i, c = c -1 and r = i, c = c+1...for each of these check if arr[r][c] == -1.
If yes then change arr[r][c] to 0 and call find(r,c)

Thus, we recursively find the entire connected component due to i,j using find(i,j) and ncrement count by 1 for each such instance.

void main()
{
	int a[7][5]={
					-1,-1,-1, 0, 0,
					-1,-1, 0,-1,-1,
					 0, 0, 0, 0,-1,
					 0, 0, 0,-1,-1,
					 0, 0, 0,-1, 0,
					 0,-1, 0, 0, 0,
					 0,-1, 0, 0, 0,
				}    ;
	   int i,j,count=0;

	   clrscr();
				for(i=0;i<6;i++)
				{
					for(j=0;j<4;j++)
					{
						if(a[i][j] == -1 && a[i][j+1] == -1)
							count++;
						if(a[i][j] == -1 && a[i+1][j] == -1)
							count++;
					}
				}
				printf("%d",count);
	getch();
}

I think it should be 8 is it?
Here's my code:

#include <iostream>
using namespace std;

int map[9][7] = {
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0,-1, 0,-1, 0, 0, 0 },
    { 0,-1,-1, 0,-1,-1, 0 },
    { 0, 0, 0, 0, 0,-1, 0 },
    { 0, 0, 0, 0,-1,-1, 0 },
    { 0, 0, 0, 0,-1, 0, 0 },
    { 0, 0,-1, 0, 0, 0, 0 },
    { 0, 0,-1, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0 },
};

int connected_count(int map[9][7]) {
    int cnt = 0;
    for (int ix = 1; ix <= 8; ++ix) {
        for (int jx = 1; jx <= 6; ++jx) {
             if (map[ix][jx] == -1) {
                 cnt -= map[ix+1][jx];
                 cnt -= map[ix][jx+1];
             }
        }
    }
    return cnt;
}

int main() {
    cout << connected_count(map) << endl;
    return 0;
}

I think the answer should be 3.

1. -1
-1 -1

2. -1 -1
-1
-1 -1
-1

3. -1
-1