java - Greedy Recursive Search -


my professor gave assignment need search around given point in grid other spots makes group (in example need find number of spots in "l" shape within problem).

so grid 10x10, , professor has given spot start with. professor gave idea check neighboring spots, , add set, if spot newly found (which in set) recursively call method.

private spot findspots(set<spot> spots, set<spot> activespots, spot initial) {     spot newspot = null;       set<spot> activeset = new hashset<spot>();     checkaround(activeset, new spot(initial.i - 1, initial.j));     checkaround(activeset, new spot(initial.i + 1, initial.j));     checkaround(activeset, new spot(initial.i, initial.j - 1));     checkaround(activeset, new spot(initial.i, initial.j + 1));       (spot spot : activeset) {         newspot = findspots(spots, activespots, spot);         if (grid[newspot.i][newspot.j] == true)             spots.add(newspot);     }      return newspot;  }  private boolean checkaround(set<spot> spots, spot spot) {     if (!spots.contains(spot)) {         spots.add(spot);         return true;     }     return false;  }

i know need boundary condition (or else stackoverflow exceptions), need in logic.

i know need boundary condition [...]

you said yourself. 1 key word boundary. need check if spot legal in grid, , stop exploring if not.

another stop condition if spot visited.

if implement these 2 stop conditions, , if perform these checks before making further recursive calls, find solution without overflowing stack.

something this:

private int countspots(set<spot> visited, spot spot) {     if (!isvalid(spot) || visited.contains(spot)) {         return 0;     }      visited.add(spot);      int count = 1;     count += countspots(visited, new spot(spot.x - 1, spot.y));     count += countspots(visited, new spot(spot.x + 1, spot.y));     count += countspots(visited, new spot(spot.x, spot.y + 1));     count += countspots(visited, new spot(spot.x, spot.y - 1));     return count; }

btw algorithm you're using variant of flood fill, see more info , tips , hints in wikipedia page.


-

Comments

Post a Comment

Popular posts from this blog

java - SSE Emitter : Manage timeouts and complete() -

i writing web app multiple listeners(evcentsource sse clients js) connected server . want store sse emitter per connected listener : can done in memory or other means assigning id each client able achieve far now question ; how send response/event specific client connected web app ? while doing sseemmiters stored either getting completed or timed out. how prevent ? how keep sseemmiter available open infinite time (till client closes) , send events selectively .
Read more

jquery - uncaught exception: DataTables Editor - remote hosting of code not allowed -

i'm trying implement crud operation using datatableseditor using datatables.but i'm getting error messages: 1)uncaught exception: datatables editor - remote hosting of code not allowed. please see http://editor.datatables.net details on how purchase editor license 2)typeerror: a.editor undefined 3) $.fn.datatable.editor not constructor" what reason? here configuration: <%@ page language="java" contenttype="text/html; charset=iso-8859-1" pageencoding="iso-8859-1"%> <!doctype html public "-//w3c//dtd html 4.01 transitional//en" "http://www.w3.org/tr/html4/loose.dtd"> <html> <head> <meta http-equiv="content-type" content="text/html; charset=iso-8859-1"> <title>insert title here</title> <link rel="stylesheet" type="text/css" href="//cdn.datatables.net/1.10.12/css/jquery.datatables.min.css"> <link re...
Read more

java - How to resolve error - package com.squareup.okhttp3 doesn't exist? -

i trying convert json java object use of gson in maven, following youtube video guidance - https://www.youtube.com/watch?v=vqgghm9pwe0 , theres error occurs when in main class error - package com.squareup.okhttp3 doesn't exist. code below: java package com.codebeasty.json; import com.squareup.okhttp3.okhttpclient; public class main { private static okhttpclient client = new okhttpclient(); public static void main (string [] args) { } } i put in dependency in pom.xml: <dependencies> <dependency> <groupid>com.squareup.okhttp3</groupid> <artifactid>okhttp</artifactid> <version>3.4.2</version> </dependency> <dependency> <groupid>com.google.code.gson</groupid> <artifactid>gson</artifactid> <version>2.8.0</version> </dependency> </dependencies> i dont understand why doesn't recognize com.squareup. there may need download? have downl...
Read more