Member Avatar for Java_tyro

Hello,

Help me in writing a logic for the program:

User input:


11000
01100
00101
10001
01011

Two 1's are said to be connected if they are adjacent to each other horizontally, vertically & diagonally.

Need to find the largest sector of 1's in the above input string.

For example: In the above input string the largest sector is of size 5.

Please help me.

Thank you

  • 3 Contributors
  • 4 Replies
  • 243 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by jon.kiparsky

Dani AI

Generated

Input parsing and the test-case boundary are the only real gaps left in the thread. The sample uses a leading test-case count but does not give per-grid dimensions, so adopt one clear rule: either require each grid to be prefixed with its row/column counts or separate grids with a blank line. While reading lines with BufferedReader, skip blank lines and trim each line; collect contiguous non-empty lines into one grid and then hand that grid (as a char[][] or String[]) to a solver method.

Treat the problem as a connected-components search with 8-direction adjacency. As suggested, use a flood-fill (DFS or BFS) and keep a visited boolean[][]; as advised, encapsulate the work in a solve(grid) method that returns the maximum component size. Iterate every cell; when an unvisited 1 is found, run flood-fill to count its size and update the max.

A compact iterative DFS (stack) avoids deep recursion on large inputs:

private int floodFill(char[][] g, int r, int c, boolean[][] vis) {
    int count = 0;
    int[] dr = {-1,-1,-1,0,0,1,1,1};
    int[] dc = {-1,0,1,-1,1,-1,0,1};
    Deque<int[]> stack = new ArrayDeque<>();
    stack.push(new int[]{r,c});
    vis[r][c] = true;
    while (!stack.isEmpty()) {
        int[] p = stack.pop();
        count++;
        for (int k = 0; k < 8; k++) {
            int nr = p[0] + dr[k], nc = p[1] + dc[k];
            if (nr >= 0 && nr < g.length && nc >= 0 && nc < g[nr].length
                && !vis[nr][nc] && g[nr][nc] == '1') {
                vis[nr][nc] = true;
                stack.push(new int[]{nr, nc});
            }
        }
    }
    return count;
}

Performance and edge notes: overall time is O(RC) and space O(RC) for visited. Prefer iterative flood-fill in Java to avoid StackOverflowError on big grids. Validate/trust input (trim lines, reject or normalize irregular row lengths) or require explicit dimensions to remove ambiguity. These steps complete the solve(grid) approach and bridge parsing to the component-count logic discussed earlier.

Recommended Answers

All 4 Replies

Member Avatar for Taywin

What is your current logic to the problem? I can give you a hint, use a search and iterate through the area until no more connected 1's is found. Don't forget to keep track of where you have already visited. The method could be recursive (easy to implement) or iterative (a bit longer).

Edited by Taywin because: n/a
Member Avatar for jon.kiparsky

Start by figuring out what the steps are at a high level, then figure out how to execute them. Executing them may, and probably will, involve decomposing them into steps which you'll then re-examine in the same way until you have methods which are trivial to execute. Write the trivial methods.
Test.
If results pass tests, done. Else, find and fix bugs.

Member Avatar for Java_tyro

Start by figuring out what the steps are at a high level, then figure out how to execute them. Executing them may, and probably will, involve decomposing them into steps which you'll then re-examine in the same way until you have methods which are trivial to execute. Write the trivial methods.
Test.
If results pass tests, done. Else, find and fix bugs.

I need to read a file for input like:

Sample Input

2 

11000 
01100 
00101 
10001 
01011  

1011
1010

Sample Output

5
3

Sample Input 2 indicates there are two grids.

        FileReader fr = new FileReader("input.txt");
        BufferedReader br = new BufferedReader(fr);
        String s;
        while( (s = br.readLine()) != null)
        {
            System.out.println(s.length());
        }

How should I proceed further now?

Edited by mike_2000_17 because: Fixed formatting
Member Avatar for jon.kiparsky

So far your breakdown is:
Get the data
Solve the problem somehow for however many grids are submitted.
Report the result.

That middle step needs a little work.
You know you're going to have to solve the problem for one gird, so maybe you should work on that. Solve that, and you should be able to extend it to multiple grids without much trouble.

I'll give you this much for free: it'll look a little like this
private int solve(Grid g) {}

where Grid might be a 2D array or a custom object or whatever structure makes it easiest for you to solve it. Return your solution as an int. When you do multiple grids, you'll stuff that in an array or an ArrayList or whatever makes most sense to you at that point. Don't worry about that now, though, just return the int so you can use it later.

But now you have your solve method to break down.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.