about summary refs log tree commit diff stats
path: root/algorithms
diff options
context:
space:
mode:
authorAndinus <andinus@nand.sh>2021-11-03 22:22:57 +0530
committerAndinus <andinus@nand.sh>2021-11-03 22:22:57 +0530
commit8cef86f0eb8b46b0ed2d7c37fa216890300249f6 (patch)
tree4d50ebc636068bcc1aa0fc8f7c8bbbc2ac252a41 /algorithms
parentc9e3cb29fedcbe7e247d5abfb61bc4f0024ce5f4 (diff)
downloadfornax-8cef86f0eb8b46b0ed2d7c37fa216890300249f6.tar.gz
java/DFS: Don't walk on visited, Add DFS solutions, change colors
It didn't walk on visited grid but printed that as an iteration so it
seemed like it did.
Diffstat (limited to 'algorithms')
-rw-r--r--algorithms/java/DFS.java7
1 files changed, 4 insertions, 3 deletions
diff --git a/algorithms/java/DFS.java b/algorithms/java/DFS.java
index ff4567d..e0da681 100644
--- a/algorithms/java/DFS.java
+++ b/algorithms/java/DFS.java
@@ -24,6 +24,9 @@ public class DFS {
                 || curx > maze.length - 1 || cury > maze[0].length - 1)
                 continue;
 
+            if (visited[curx][cury])
+                continue;
+
             // Marker cells.
             if (maze[curx][cury] == '$')
                 System.out.print("|");
@@ -43,9 +46,7 @@ public class DFS {
             if (maze[curx][cury] == '$')
                 System.exit(0);
 
-            if (visited[curx][cury]) {
-                continue;
-            } else if (maze[curx][cury] == '.') {
+            if (maze[curx][cury] == '.') {
                 visited[curx][cury] = true;
                 traverse(curx, cury, maze, visited);
                 visited[curx][cury] = false;
generated by cgit-pink 1.4.1-2-gfad0 (git 2.36.2.497.gbbea4dcf42) at 2024-06-26 12:11:15 +0000
am <vc@akkartik.com> 2021-05-16 07:16:49 -0700 committer Kartik K. Agaram <vc@akkartik.com> 2021-05-16 07:23:43 -0700 Bresenham's algorithm for bezier curves' href='/akkartik/mu/commit/bezier.c?h=hlt&id=2ab8747b4aa6d662253a90551a51f7ae981ab596'>2ab8747b ^ 
ba3f67ca ^

2ab8747b ^















ba3f67ca ^

2ab8747b ^


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

                                                             









                                                                      
                                                                           



                                                                           
                                                                      



                                                                            
                                                                                 


                                                                           




                                                                                   
                                                                           
                         

                                               
                                                                                   














                                                                               
                                                            

           
/* From http://members.chello.at/easyfilter/bresenham.html */
#include<assert.h>
#include<stdio.h>

void setPixel(int x, int y) {
  printf("%d %d\n", x, y);
}

void plotQuadBezierSeg(int x0, int y0, int x1, int y1, int x2, int y2)
{                            
  int sx = x2-x1, sy = y2-y1;
  long xx = x0-x1, yy = y0-y1, xy=0;       /* relative values for checks */
  double dx, dy, err, cur = xx*sy-yy*sx;                    /* curvature */

  assert(xx*sx <= 0 && yy*sy <= 0);  /* sign of gradient must not change */

  printf("A sx %d sy %d xx %ld yy %ld cur %g\n", sx, sy, xx, yy, cur);
  if (sx*(long)sx+sy*(long)sy > xx*xx+yy*yy) { /* begin with longer part */ 
    printf("swap\n");
    x2 = x0; x0 = sx+x1; y2 = y0; y0 = sy+y1; cur = -cur;  /* swap P0 P2 */
  }  
  printf("B sx %d sy %d xx %ld yy %ld xy %ld cur %g\n", sx, sy, xx, yy, xy, cur);
  if (cur != 0) {                                    /* no straight line */
    xx += sx; xx *= sx = x0 < x2 ? 1 : -1;           /* x step direction */
    yy += sy; yy *= sy = y0 < y2 ? 1 : -1;           /* y step direction */
    printf("E sx %d sy %d xx %ld yy %ld xy %ld cur %g\n", sx, sy, xx, yy, xy, cur);
    xy = 2*xx*yy;
    printf("F sx %d sy %d xx %ld yy %ld xy %ld cur %g\n", sx, sy, xx, yy, xy, cur);
                  xx *= xx; yy *= yy;          /* differences 2nd degree */
    printf("M sx %d sy %d xx %ld yy %ld xy %ld cur %g\n", sx, sy, xx, yy, xy, cur);
    if (cur*sx*sy < 0) {                           /* negated curvature? */
      printf("negate\n");
      xx = -xx; yy = -yy; xy = -xy; cur = -cur;
    }
    printf("N sx %d sy %d xx %ld yy %ld xy %ld cur %g\n", sx, sy, xx, yy, xy, cur);
    dx = 4.0*sy*cur*(x1-x0)+xx-xy;             /* differences 1st degree */
    dy = 4.0*sx*cur*(y0-y1)+yy-xy;
    xx += xx; yy += yy; err = dx+dy+xy;                /* error 1st step */    
    do {                              
      printf("%d %d: dx %g dy %g err %g\n", x0, y0, dx, dy, err);
      if (x0 == x2 && y0 == y2) return;  /* last pixel -> curve finished */
      y1 = 2*err < dx;                  /* save value for test of y step */
      if (2*err > dy) { x0 += sx; dx -= xy; err += dy += yy; } /* x step */
      if (    y1    ) { y0 += sy; dy -= xy; err += dx += xx; } /* y step */
    } while (dy < dx );           /* gradient negates -> algorithm fails */
  }
//?   plotLine(x0,y0, x2,y2);                  /* plot remaining part to end */
}

int main(void) {
  plotQuadBezierSeg(0x200, 0x20, 0x180, 0x90, 0x180, 0x160);
  return 0;
}