[蓝桥杯2017初赛]迷宫 java+dfs+剪枝

问题描述

X星球的一处迷宫游乐场建在某个小山坡上。它是由10x10相互连通的小房间组成的。

房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则：

L表示走到左边的房间，R表示走到右边的房间，U表示走到上坡方向的房间，D表示走到下坡方向的房间。

X星球的居民有点懒，不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此！

开始的时候，直升机把100名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。

迷宫地图如下：

UDDLUULRUL

UURLLLRRRU

RRUURLDLRD

RUDDDDUUUU

URUDLLRRUU

DURLRLDLRL

ULLURLLRDU

RDLULLRDDD

UUDDUDUDLL

ULRDLUURRR

请你计算一下，最后，有多少玩家会走出迷宫? 而不是在里边兜圈子。

输出

输出一个整数表示答案

提示

为方便理解，可参考此图

```java
在这里插入代码片
import java.util.*;
public class Main {
	public static String mapp[]= {
			"UDDLUULRUL",
			"UURLLLRRRU",
			"RRUURLDLRD",
			"RUDDDDUUUU",
			"URUDLLRRUU",
			"DURLRLDLRL",
			"ULLURLLRDU",
			"RDLULLRDDD",
			"UUDDUDUDLL",
			"ULRDLUURRR"}; //地图
	public static int vis[][]=new int [162][162]; //标记地图该点有没有走过 1表示走过 0表示没有
	public static int num[][]=new int [162][162]; //标记地图该点的状况 1表示可以走出去 -1表示不可以走出去 
	                                              //0表示目前还不知道情况
	public static int dfs(int x,int y) {          //递归搜索
		int xx=0,yy=0;
		switch (mapp[x].charAt(y)) {              //4个方向
		case 'U':
			 xx=x-1; yy=y;
			break;
		case 'L':
			 xx=x; yy=y-1;
			break;
		case 'D':
			 xx=x+1; yy=y;
			break;
		case 'R':
			 xx=x; yy=y+1;
			break;
		default:
			break;
		}
		
			if(xx==-1||yy==-1||xx==10||yy==10)  
			{
			     //如果该方向的下一步越界了 也就是==0 || ==10 表示可以走出
			     //同时要标记该点走过vis[x][y]=1 num[x][y]=1 还要记得return 1
				 num[x][y]=1;
				 vis[x][y]=1;
				 return 1 ;
			}
			if(num[xx][yy]!=0)
			{
			     //如果该点num[xx][yy]不等于0 表示该点可能可以出去也可能不可以
			     //同时要标记该点走过vis[x][y]=1 num[x][y]=num[xx][yy] 还要记得return num[x][y]
				num[x][y]=num[xx][yy];
				vis[x][y]=1;
			    return num[x][y];
			}
			if(num[xx][yy]==0&&vis[xx][yy]==1)
			{
			     //如果该点num[xx][yy]等于0并且vis[xx][yy]等于1 表示没有状况但是已经走过了 表示循环了
			     //同时要标记该点走过vis[x][y]=1 num[x][y]=num[xx][yy]=-1 还要记得return num[x][y]
				num[x][y]=-1;
				num[xx][yy]=-1;
				vis[x][y]=vis[xx][yy]=1;
				return num[x][y];
			}
			if(num[xx][yy]==0&&vis[xx][yy]==0)
			{
			    //如果该点num[xx][yy]等于0并且vis[xx][yy]等于0 表示没有状况并且已经走过了表示要继续走
			    //同时要标记该点走过vis[x][y]=1 num[x][y]=dfs(xx,yy) 还要记得return num[x][y]
				vis[x][y]=1;
				num[x][y]=dfs(xx,yy);
				
				return num[x][y];
			}else
				return 0;
	}
  public static void main(String[] args) {
	  Scanner sc = new Scanner(System.in);
	  for(int i=0;i<10;i++)
		  for(int j=0;j<10;j++)
		  {
			  if(num[i][j]==0)  //如果不知道状态 就dfs
			  {
				  vis[i][j]=1;
				  num[i][j]=dfs(i,j);
			  }
		  }
	  int ans=0;
	  for(int i=0;i<10;i++) {
		  for(int j=0;j<10;j++)
		  {
			  if(num[i][j]==1)
				  ans++;
			 // System.out.print(num[i][j]+" ");
		  }
		// System.out.println();
	  }
	  System.out.println(ans);
}
  
}