C++解答

#include<iostream>
using namespace std; 
const int N = 51;
int map[N][N],book[N][N];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int head=1,tail=1;
int n,sx,sy,fx,fy,tx,ty,flag;
struct queue
{
	int x;
	int y;
	int s;
}que[2501];
int main()
{
	cin>>n;
	sx=1;sy=1;fx=1;fy=n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>map[i][j];
	que[tail].x=1;
	que[tail].y=1;
	que[tail++].s=0;
	book[sx][sy]=1;
	flag=0;
	while(head<tail){
		for(int i=0;i<=3;i++){
			tx=que[head].x+dir[i][0];
			ty=que[head].y+dir[i][1];
			if(tx<1||tx>n||ty<1||ty>n)
				continue;
			if(map[tx][ty]==0&&book[tx][ty]==0){
				book[tx][ty]=1;
				que[tail].x=tx;
				que[tail].y=ty;
				que[tail].s=que[head].s+1;
				tail++;
			}
			if(tx==fx&&ty==fy){
				flag=1;
				break;
			}
		}
		if(flag==1)
			break;
		head++;
	}
	cout<<que[tail-1].s<<endl;
	return 0;
}

Java解答

import java.util.Scanner;

//图的搜索和回溯问题
public class Main {
	static int n;
	static int sum=0;
	static int sx[]={-1,-1,-1,0,0,1,1,1};
	static int sy[]={-1,0,1,-1,1,-1,0,1};
	static int [][]s=new int[15][15];//存储本身
	static int [][]a=new int[15][15];//是否访问过标记
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		 while(scanner.hasNext())
		    {
			 	n=scanner.nextInt();
		        sum=0;
		        s=new int[15][15];
		        a=new int[15][15];
		        for(int i=0;i<n;i++)
		            for(int j=0;j<n;j++)
		                s[i][j]=scanner.nextInt();
		        a[0][0]=1;//左上角访问过，置为1；
		        dfs(0,0);
		        System.out.println(sum);
		    }
	}
	
	static void  dfs(int x,int y)//起始点x和y
	{
	    if(x==0&&y==n-1)
	    {//如果达到终点x和y的要求，执行相关操作，本体要求是路径条数
	        sum++;
	        return ;
	    }
	    for(int i=0;i<8;i++)//依次访问该点周围八个方向
	    {
	        int nx=x+sx[i];
	        int ny=y+sy[i];
	        if(nx>=0&&nx<n&&ny>=0&&ny<n&&s[nx][ny]==0&&a[nx][ny]==0)//前四个为判断是否在迷宫中  最后一个是判断该点是否被访问过
	        {
	            a[nx][ny]=1;
	            dfs(nx,ny);//是没访问过的点并且是可行点，就继续搜索
	            a[nx][ny]=0;//回溯，重新置为0，方便下次访问
	        }
	    }
	    return ;
	}
}