dfs标记路径

参考代码:

import java.util.Scanner;

public class Main {

static int[][] g=new int[51][51];//地图

static int[][] st=new int[51][51];//地图

static int[]c=new int[1010];

static int[]b=new int[1010];

static int[]d=new int[1010];

static int[]a=new int[1010];

static int[] dx= {0,1,0,-1};

static int[] dy= {1,0,-1,0};

static int n,m;//城堡大小

static int x1,y1,x2,y2,x3,y3;

static int min=(int)1e9;

static int min1=(int)1e9;

static char[]path=new char[1010];

static char[]pathmin=new char[1010];

static int count=0;

static boolean f=false;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n=5;m=5;

for(int i=1;i<=n;i++) {

        for(int j=0;j<=m-1;j++) {

        g[i][j+1]=sc.nextInt();

        }

}

dfs1(1,1,0);

int a=0,b=0;

for(int i=1;i<=min;i++) {

    System.out.println("("+a+","+" "+b+")");

    if(pathmin[i]=='x')a++;

    else if(pathmin[i]=='y')b++;

    else if(pathmin[i]=='s')a--;

    else b--;

}

System.out.println("("+4+","+" "+4+")");

}

public static void dfs1(int x,int y,int step) {

    if(step>min)return;

    if(x==5&&y==5) {

    min=Math.min(min, step);

for(int i=1;i<=count;i++) {pathmin[i]=path[i];}

    return;

    }

    for(int i=0;i<4;i++) {

    int a=x+dx[i],b=y+dy[i];

    if(g[a][b]==1||st[a][b]==1||a<1||a>n||b<1||b>m)continue;

    if(dx[i]==0&&dy[i]==1) {count++;path[count]='y';}

    else if(dx[i]==1&&dy[i]==0) {count++;path[count]='x';}

    else if(dx[i]==0&&dy[i]==-1) {count++;path[count]='z';}

    else {count++;path[count]='s';}

    st[a][b]=1;

    dfs1(a,b,step+1);

    count--;

    st[a][b]=0;

    }

}

}