P1238 迷宫记录(记录自己刷过的题)

题目描述

有一个仅由数字000与111组成的n×nn \times nn×n格迷宫。若你位于一格0上，那么你可以移动到相邻444格中的某一格111上，同样若你位于一格1上，那么你可以移动到相邻444格中的某一格000上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。 输入格式

第111行为两个正整数n,mn,mn,m。

下面nnn行，每行nnn个字符，字符只可能是000或者111，字符之间没有空格。

接下来mmm行，每行222个用空格分隔的正整数i,ji,ji,j，对应了迷宫中第iii行第jjj列的一个格子，询问从这一格开始能移动到多少格。 输出格式

mmm行，对于每个询问输出相应答案。

输入输出样例

输入 #1

2 2 01 10 1 1 2 2

输出 #1

4 4

说明/提示

所有格子互相可达。

对于20 %的数据，n≤10n≤10n≤10；

对于40@@%的数据，n≤50n≤50n≤50；

对于50PP%的数据，m≤5m≤5m≤5；

对于60``%的数据，n≤100,m≤100n≤100,m≤100n≤100,m≤100；

对于10000%的数据，n≤1000,m≤100000n≤1000,m≤100000n≤1000,m≤100000。

代码（java）

import java.util.Scanner; import java.util.Stack; public class Main { static point start; static point end; static int[][]vis; static int[][]a; static int[] xx = {0, -1, 0, 1}; static int[] yy = {-1, 0, 1, 0}; static int N ; static int M; static int ans = 0; static Stack<point> stack; static public void display( Stack<point> stack){ ans++; int size = stack.size(); int i = 0; for (point p : stack) { i++; //由于我从(0,0)开始 题目是(1,1)开始 所以x,y都加一 System.out.print("("+(p.x+1)+","+(p.y+1)+")"); if(i<size){ System.out.print("->"); } } System.out.println(); } static public void dfs(point p){ //当前点等于终点 记数++，并结束当前函数 if(p.x == end.x && p.y == end.y){ Stack out = stack; display(out); return ; } //4个方向查找 for(int i=0;i<4;i++){ int dx = p.x + xx[i]; int dy = p.y + yy[i]; point po = new point(dx,dy); //vis的值 0表示可以访问 1和2表示不能访问 if( dx>-1 && dx<N && dy>-1 && dy<M && vis[dx][dy] ==0 && a[dx][dy]==1 ){ //标记这个点被访问了 vis[dx][dy] = 1; stack.push(po); dfs(po); //函数回溯 vis[dx][dy] = 0; stack.pop(); } } } //第一行N、M和T，N为行，M为列，T为障碍总数。 //第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。 public static void main(String args[]) { Scanner in = new Scanner(System.in); N = in.nextInt(); M = in .nextInt(); vis = new int[N+50][M+50]; //栈用来记录并弹出路径 stack = new Stack<point>(); a = new int[N+50][M+50]; start = new point(); end = new point(); for(int i=0;i<N;i++) for(int j=0;j<M;j++){ a[i][j] = in.nextInt(); } //-1 是为了和数组下表对应 start.x = in.nextInt()-1; start.y = in.nextInt()-1; end.x = in.nextInt()-1; end.y = in.nextInt()-1; vis[start.x][start.y] = 1; stack.push(start); dfs(start); if(ans==0)System.out.println(-1); } } //自定义点类 class point{ int x; int y; public point(int a,int b){ x=a; y=b; } public point(){ } }