从（1,1）进入，从（n，m）出来，并且指向（n，m）
下图为6种水管状态，前4种为弯管道，后两种为直管道
代码：
1 import java.util.Iterator; 2 import java.util.LinkedList; 3 import java.util.Scanner; 4 import java.util.TreeSet; 5 import java.util.Scanner; 6 public class One { 7 //n,m为实际管道地图大小，a用于存放实际地图，book用于标记是否已经经过某管道 8 public static int n,m,a[][]=new int[51][51],book[][]=new int[51][51]; 9 //x，y表示正处于的管道的位置，front表示从哪里进入管道（1表示从左进入，2表示从上进入，3表示从右进入，4表示从下进入） 10 public static void f(int x,int y,int front){ 11 if(x==n&&y==(m+1)){//若到达出口（目的地(n,m+1)）,则输出放置管道方案 12 System.out.println("找到铺设方案，铺设方案为(其中“(,)”为经过的地标，“[]”内为管道类型状态):"); 13 for(int i=1;i<=n;i++){ 14 for(int j=0;j<=m;j++){ 15 if(book[i][j]==1)System.out.print("("+i+","+j+") ["+a[i][j]+"] "); 16 } 17 } 18 return; 19 } 20 //如果出界或者碰到树（a[x][y]==0），返回 21 if(x<1||y<1||x>n||y>m||a[x][y]==0)return; 22 //如果已经使用了该点的管道，返回 23 if(book[x][y]==1)return; 24 book[x][y]=1;//若没有出界，也没有使用过该管道，则标记使用该管道 25 26 //遇到直管道的情况 27 if(a[x][y]==5||a[x][y]==6){ 28 if(front==1){//左进,只能使用管道5 29 a[x][y]=5; 30 f(x,y+1,1); 31 } 32 if(front==2){//上进,只能使用管道6 33 a[x][y]=6; 34 f(x+1,y,2); 35 } 36 if(front==3){//右进,只能使用管道5 37 a[x][y]=5; 38 f(x,y-1,3); 39 } 40 if(front==4){//下进,只能使用管道6 41 a[x][y]=6; 42 f(x-1,y,4); 43 } 44 } 45 46 //遇到弯管道的情况 47 if(a[x][y]>=1&&a[x][y]<=4){ 48 if(front==1){//左进，可用3,4两种状态 49 a[x][y]=3; 50 f(x+1,y,2);//3时，下一个点只能上进 51 a[x][y]=4; 52 f(x-1,y,4);//4时，下一个点只能下进 53 } 54 if(front==2){//上进，可用1,4两种状态 55 a[x][y]=1;//1时，下一个点只能左进 56 f(x,y+1,1); 57 a[x][y]=4;//4时，下一个点只能右进 58 f(x,y-1,3); 59 } 60 if(front==3){//右进，可用1,2两种状态 61 a[x][y]=1;//1时，下一个点只能下进 62 f(x-1,y,4); 63 a[x][y]=2;//2时，下一个点只能上进 64 f(x+1,y,2); 65 } 66 if(front==4){//下进，可用2,3两种状态 67 a[x][y]=2;//2时，下一个点只能左进 68 f(x,y+1,1); 69 a[x][y]=3;//3时，下一个点只能右进 70 f(x,y-1,3); 71 } 72 } 73 return; 74 } 75 public static void main(String args[]){ 76 Scanner scanner=new Scanner(System.in); 77 System.out.println("请输入水管道地下图行列:"); 78 n=scanner.nextInt(); 79 m=scanner.nextInt(); 80 System.out.println("请输入水管道地下图（0为树，有六种管道状态，1-4为弯管道，5-6为直管道）:"); 81 for(int i=1;i<=n;i++){ 82 for(int j=1;j<=m;j++){ 83 a[i][j]=scanner.nextInt(); 84 } 85 System.out.println(""); 86 } 87 f(1,1,1);//地图从（1,1）开始，并且从左边进入 88 } 89 }
运行结果如下图：
