2013
12-13

# 九度-1335-闯迷宫（40分）[解题代码]

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

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

//============================================================================
// Name        : jd-1335-闯迷宫.cpp
// Author      : coder
// Version     :
// 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选项是不对的。