# Algorithm - Plumbing game

Reference: Aha! Algorithm "

## 1, topic

The plumber's game refers to the matrix as shown in the figure below. There are two kinds of pipes, one is straight and the other is curved. All pipes can rotate freely, and the final goal is to connect the water inlet to the water outlet. The trees are obstacles.  ## 2. Algorithm idea

In this paper, the depth first search algorithm is used to identify the direction of the water inlet, expand according to the direction of the water inlet each time when exploring a new pipeline, and then judge the direction of the next node according to the type of pipeline.

## 3, code

```package search.Breadth first search BFS.Plumber's game;

import java.util.Scanner;

public class Main {
private static int[][] map;         //Storage pipeline diagram
private static int n, m, top;       //Matrix x, y, top stack top element of pipeline
private static boolean[][] status;  //Used or not
private static String[] stack;      //Stack

/**
*
* @param x Coordinate x
* @param y Coordinate y
* @param direction Water inlet direction: 1 up, 2 right, 3 down, 4 left
*/
private static void  dfs(int x, int y, int direction){
if(x == n-1 && y == m){     //If to the next exit, it means to complete a path
System.out.println("Search to connectivity route");
for (int i = 0; i < top;i++){
System.out.print(stack[i]+"->");
}
System.out.println();
return ;
}

if(y < 0 || x < 0|| x > n-1 || y > m-1 || status[x][y])
return;

status[x][y] = true;
stack[top] = "("+(x+1)+","+(y+1)+","+direction+")";     //Push
top++;

if (5 <= map[x][y] && map[x][y] <= 6){      //If it's straight pipe
switch (direction){
case 1:
dfs(x+1, y, direction);
break;
case 2:
dfs(x, y-1, direction);
break;
case 3:
dfs(x-1, y, direction);
break;
case 4:
dfs(x, y+1, direction);
break;
}

}else{
switch (direction){     //Curved pipe
case 1:
dfs(x, y-1, 2);
dfs(x, y+1, 4);
break;
case 2:
dfs(x-1, y, 3);
dfs(x+1, y, 1);
break;
case 3:
dfs(x, y-1, 2);
dfs(x, y+1, 4);
break;
case 4:
dfs(x-1, y, 3);
dfs(x+1, y, 1);
break;
}
}

status[x][y] = false;
top--;
}

public static void main(String[] ages){
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();

map = new int[n][m];
status = new boolean[n][m];
stack = new String[n*m];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
map[i][j] = scanner.nextInt();
}
}

dfs(0,0, 4);
}
}

/**
Test data:
5 4
5 3 5 3
1 5 3 0
2 3 5 1
6 1 1 5
1 5 5 4
Result:
Search to connectivity route
(1,1,4)->(1,2,4)->(2,2,1)->(3,2,1)->(3,3,4)->(3,4,4)->(4,4,1)->(5,4,1)->
*/```

Keywords: Java

Added by robin01 on Wed, 01 Apr 2020 17:45:42 +0300