Plumber Game

Original

The general rule of the game is that a rectangular piece of land is divided into N*M unit squares, and now there are some water pipes buried on it, which will run from coordinates

The upper left edge of the rectangular land of (0,0) extends to the lower right edge of the rectangular land of coordinates (N-1,M-1).There are only 2 types of water pipes, as follows

As shown.

Each type of pipe will occupy a square unit of land.These pipes can now be rotated to form a piping system, that is, to create a piping system from (0,0) to (N-1,M-1)

Connecting pipe.The squares with trees indicate that there are no pipes.The following figure shows a tree in a 5*4 field (2,4).

We can rotate some of these pipes to form a connected pipe system, as shown in the following figure:

The first line of input consists of two integers, N and M, and the next N lines, each with M integers representing each small cell in the map.0 represents trees,

1~6 represents the six different placement modes of the pipeline, as follows:

Solving ideas:

The deep search (a stroke of the question) is used to solve the problem, but the direction of the deep search on this question can only be in two cases at most due to the direction restriction of the water inlet.

There is no need to set the direction array; since there are only two states for water pipes, elbow and straight pipes, simply enumerate these two states, in which

By enumerating the four directions of the water pipe, you can determine which lattice the water will flow to next, and then continue the enumeration.

import java.util.*;

public class Plumber Game {
    
    static int count=0;
    static int flag=0;
    static int n;
    static int m;
    static int maze[][];
    static int book[][];
    static ArrayList listx=new ArrayList();
    static ArrayList listy=new ArrayList();
    
    static void dfs(int x,int y,char way) {    //way Represents the water inlet
        if(x==n-1 && y==m) {    //Success Judgment
            flag=1;
            return;
        }
        if(x<0 || x>n-1 || y<0 || y>m-1) {    //Judgment over borders
            return;
        }
        if(maze[x][y]==0 || book[x][y]==1) {    //Trees and Access Judgment
            return;
        }
        book[x][y]=1;
        listx.add(x);
        listy.add(y);
        count++;
        if(maze[x][y]==5 || maze[x][y]==6) {    //Straight pipe
            if(way=='l') {    //Left
                dfs(x,y+1,'l');
            }
            if(way=='r') {    //right
                dfs(x,y-1,'r');
            }
            if(way=='u') {    //upper
                dfs(x+1,y,'u');
            }
            if(way=='d') {    //lower
                dfs(x-1,y,'d');
            }
        }
        if(maze[x][y]>=1 && maze[x][y]<=4){    //Elbow
            if(way=='l') {    //Left
                dfs(x-1,y,'d');
                dfs(x+1,y,'u');
            }
            if(way=='r') {    //right
                dfs(x-1,y,'d');
                dfs(x+1,y,'u');
            }
            if(way=='u') {    //upper
                dfs(x,y-1,'r');
                dfs(x,y+1,'l');
            }
            if(way=='d') {    //lower
                dfs(x,y-1,'r');
                dfs(x,y+1,'l');
            }
        }
        if(flag==1) {
            return;
        }
        book[x][y]=0;    //To flash back
        listx.remove(count-1);
        listy.remove(count-1);
        count--;
        return;
    }

    public static void main(String[] args) {
        Scanner reader=new Scanner(System.in);
        n=reader.nextInt();
        m=reader.nextInt();
        maze=new int[n][m];
        book=new int[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                maze[i][j]=reader.nextInt();
                book[i][j]=0;
            }
        }
        dfs(0,0,'l');
        if(flag==1) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
        System.out.print("The path is:");
        for(int i=0;i<count;i++) {
            System.out.print("("+listx.get(i)+","+listy.get(i)+")"+" ");
        }
    }
}

Test cases:

Input:

5 4
5 3 5 3
1 5 3 0
2 3 5 1
6 1 1 5
1 5 5 4

Output:
YES
The path is: (0,0) (0,1) (1,1) (2,1) (2,2) (2,3) (3,3) (4,3)

11:05:05

2018-07-22

Tags: Java

Posted on Sat, 01 Feb 2020 08:37:26 -0800 by MattAdamson