小测一下_牛客博客

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**

@Author: zhouLai
@Date: 2020/3/23 20:05
@Version 1.0
/
public class Main {
/*
- 定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：
  
  int maze[5][5] = {
```
      0, 1, 0, 0, 0,
      0, 1, 0, 1, 0,
      0, 0, 0, 0, 0,
      0, 1, 1, 1, 0,
      0, 0, 0, 1, 0,
```
  };
  它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
  入口点为[0,0],既第一空格是可以走的路。
  
  Input
```
  一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
```
  Output
```
  左上角到右下角的最短路径，格式如样例所示。
```
  Sample Input
  0 1 0 0 0
  0 1 0 1 0
  0 0 0 0 0
  0 1 1 1 0
  0 0 0 1 0
  Sample Output
  (0, 0)
  (1, 0)
  (2, 0)
  (2, 1)
  (2, 2)
  (2, 3)
  (2, 4)
  (3, 4)
  (4, 4)
  输入描述:
  输入两个整数，分别表示二位数组的行数，列数。
  再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
  输出描述:
  左上角到右下角的最短路径，格式如样例所示。*/
  static Integer[][] map;
  static Integer N,M;
  public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  while (sc.hasNext()){
```
  N = sc.nextInt();
  M = sc.nextInt();
  map = new Integer[N][M];
  for (Integer i = 0; i < N; i++) {
      for (Integer j = 0; j < M; j++) {
          map[i][j] = sc.nextInt();
      }
  }
  dfs(0,0); //将走不通的路封死
  sout(0,0);//打印唯一的道路
```
  }
  }
  
  private static void dfs(int x, int y) {
  if (x==N-1&&y==M-1){
```
  return;
```
  }
  //向下
  if(x+1<N){
```
  if (map[x+1][y]!=1){
      dfs(x+1,y);
  }
```
  }
  
  //向右
  if(y+1<M){
```
  if (map[x][y+1]!=1){
      dfs(x,y+1);
  }
```
  }
  
  //不能向下并且不能向右
  if((x+1==N && map[x][y+1]==1)){ //不能向下
```
  map[x][y] = 1;
```
  }
  
  //不能向下也不能向右，也不在终点
  if(x+1!=N && y+1!=M){
```
  if((map[x+1][y]==1 && map[x][y+1]==1 )){
      map[x][y] = 1;
  }
```
  }
  
  }
  
  private static void sout(int x, int y) {
  if (x==N-1&&y==M-1){
```
  System.out.println("("+x+","+y+")");
  return;
```
  }
  //向下
  if(x+1<N){
```
  if (map[x+1][y]!=1){
      System.out.println("("+x+","+y+")");
      sout(x+1,y);
  }
```
  }
  
  //向右
  if(y+1<M){
```
  if (map[x][y+1]!=1){
      System.out.println("("+x+","+y+")");
      sout(x,y+1);
  }
```
  }

}