首页 > 搜索 > BFS搜索 > 九度-1335-闯迷宫(40分)[解题代码]
2013
12-13

九度-1335-闯迷宫(40分)[解题代码]

题目描述:
sun所在学校每年都要举行电脑节,今年电脑节有一个新的趣味比赛项目叫做闯迷宫。sun的室友在帮电脑节设计迷宫,所以室友就请sun帮忙计算下走出迷宫的最少步数。

知道了最少步数就可以辅助控制比赛难度以及去掉一些没有路径到达终点的map。

比赛规则是:从原点(0,0)开始走到终点(n-1,n-1),只能上下左右4个方向走,只能在给定的矩阵里走。

输入:
输入有多组数据。每组数据输入n(0<n<=100),然后输入n*n的01矩阵,0代表该格子没有障碍,为1表示有障碍物。

注意:如果输入中的原点和终点为1则这个迷宫是不可达的。

输出:
对每组输入输出该迷宫的最短步数,若不能到达则输出-1。
样例输入:
2
0 1
0 0
5
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
0 1 1 1 0
1 0 1 0 0
样例输出:
2
8

简单的BFS搜索题目。

//============================================================================
// Name        : jd-1335-闯迷宫.cpp
// Author      : coder
// Version     :
// Copyright   : www.acmerblog.com
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
int n;
int map[101][101],x,y;
int dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };
class Point{
public:int x,y,len;
	Point(int _x,int _y,int _len){
		x = _x; y=_y; len=_len;
	}
};

int bfs(queue<Point> Q){
	Q.push( Point(0,0,0) );
	while(!Q.empty()){
		Point f = Q.front();
		Q.pop();
		//cout << f.x << " " << f.y << endl;
		for(int i=0; i<4; i++){
			x = f.x + dir[i][0];
			y = f.y + dir[i][1];
			if(x==n-1 && y==n-1) return f.len+1;
			if(x >=0 && y >=0 && x < n && y<n && !map[x][y]){
				Q.push( Point(x,y,f.len+1) );
				map[x][y] = 1;
			}
		}
	}
	return -1;
}
int main() {
	freopen("in.txt","r", stdin);
	while(cin >> n){
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				scanf("%d", &map[i][j]);
		if(map[0][0]){
			puts("-1");continue;
		}
		queue<Point> Q;
		printf("%d\n",bfs(Q));
	}
	return 0;
}

 

cpp 代码2如下:

#include<stdio.h>
#include<queue>
#define INF 0x7fffffff
using namespace std;
struct S {
	int x, y;
	S(int i, int j) {
		x = i, y = j;
	}
};
int M[102][102], D[102][102], n, i, j, t;
int main() {
	while (~scanf("%d", &n)) {
		for (i = 0; i < n; ++i)
			for (j = 0; j < n; ++j)
				D[i][j] = INF,scanf("%d", &M[i][j]);
		queue<S> r;
		--n;
		if (M[0][0] || M[n][n]) {
			puts("-1");
			continue;
		}
		r.push(S(0, 0));
		D[0][0] = 0;
		while (!r.empty()) {
			i = r.front().x, j = r.front().y;
			r.pop();
			t = D[i][j] + 1;
			if (i - 1 >= 0 && !M[i - 1][j] && D[i - 1][j] > t)
				D[i - 1][j] = t, r.push(S(i - 1, j));
			if (j - 1 >= 0 && !M[i][j - 1] && D[i][j - 1] > t)
				D[i][j - 1] = t, r.push(S(i, j - 1));
			if (i + 1 <= n && !M[i + 1][j] && D[i + 1][j] > t)
				D[i + 1][j] = t, r.push(S(i + 1, j));
			if (j + 1 <= n && !M[i][j + 1] && D[i][j + 1] > t)
				D[i][j + 1] = t, r.push(S(i, j + 1));
		}
		if (D[n][n] >= INF)
			D[n][n] = -1;
		printf("%d\n", D[n][n]);
	}
}
/**************************************************************
	Problem: 1335
	User: coder
	Language: C++
	Result: Accepted
	Time:70 ms
	Memory:1136 kb
****************************************************************/

 


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。