献给阿尔吉侬的花束
献给阿尔吉侬的花束
阿尔吉侬是一只聪明又慵懒的小白鼠,它最擅长的就是走各种各样的迷宫。
今天它要挑战一个非常大的迷宫,研究员们为了鼓励阿尔吉侬尽快到达终点,就在终点放了一块阿尔吉侬最喜欢的奶酪。
现在研究员们想知道,如果阿尔吉侬足够聪明,它最少需要多少时间就能吃到奶酪。
迷宫用一个 R×C 的字符矩阵来表示。
字符 S 表示阿尔吉侬所在的位置,字符 E 表示奶酪所在的位置,字符 # 表示墙壁,字符 . 表示可以通行。
阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置,但不能走出地图边界。
输入格式
第一行是一个正整数 T,表示一共有 T 组数据。
每一组数据的第一行包含了两个用空格分开的正整数 R 和 C,表示地图是一个 R×C 的矩阵。
接下来的 R 行描述了地图的具体内容,每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。
输出格式
对于每一组数据,输出阿尔吉侬吃到奶酪的最少单位时间。
若阿尔吉侬无法吃到奶酪,则输出“oop!”(只输出引号里面的内容,不输出引号)。
每组数据的输出结果占一行。
数据范围
1<T≤10,
2≤R,C≤200
输入样例:
3
3 4
.S…
###.
…E.
3 4
.S…
.E…
…
3 4
.S…
…E.
输出样例:
5
1
oop!
算法思路
用 g[N][N] 接收地图。
d[N][N] 存储到每个点的路径长度。
从起点出发,广度优先遍历地图:
起点入队。
如果队列非空,一直执行下面语句:
队头出队。
遍历队头的上下左右四个方向:如果是 ‘.’ 走过去,并且该位置入队,该点对应的d值更新为队头的d + 1,该点更新为’#’,表示走过了。如果是 ‘#’ 不做处理,如果是 ‘E’,走到了终点,输出该点对应的 d 值。
如果队列为空,还没有找到终点,则无法到达,输出 oop!。
提交代码
C++
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 210;
typedef pair<int, int> PII;
int t, a, c;
char g[N][N];
int d[N][N];
PII start, tend;
int bfs()
{
queue<PII> q;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
memset(d, -1, sizeof d);
d[start.first][start.second] = 0;
q.push(start);
while(q.size())
{
auto cur = q.front();
q.pop();
for (int i = 0; i < 4; ++ i)
{
int x = cur.first + dx[i];
int y = cur.second + dy[i];
if (x > 0 && x <= a && y > 0 && y <= c && d[x][y] == -1
&& (g[x][y] == '.' || g[x][y] == 'E'))
{
d[x][y] = d[cur.first][cur.second] + 1;
if (g[x][y] == 'E') return d[x][y];
q.push(make_pair(x, y));
}
}
}
return d[tend.first][tend.second];
}
int main()
{
scanf ("%d", &t);
while(t-- > 0)
{
scanf ("%d%d", &a, &c);
for (int i = 1; i <= a; ++ i)
{
for (int j = 1; j <= c; ++ j)
{
scanf (" %c", &g[i][j]); // 输入的时候不要忘记这个%c前面的空格
if (g[i][j] == 'S') start = make_pair(i, j);
else if (g[i][j] == 'E') tend = make_pair(i, j);
}
}
int res = bfs();
if (res == -1 || res == 0) puts("oop!");
else printf ("%d\n", res);
}
return 0;
}
Java
import java.util.*;
import java.io.*;
public class Main
{
static int N = 210;
static int [][] d = new int [N][N];
static char [][] g = new char [N][N];
static PII start;
static PII tend;
static int t, a, c;
static int bfs()
{
Queue<PII> q = new LinkedList<PII>();
int [] dx = {-1, 0, 1, 0};
int [] dy = {0, 1, 0, -1};
for (int i = 0; i < a; ++ i) Arrays.fill(d[i], -1);
q.add(start);
d[start.first][start.second] = 0;
while(!q.isEmpty())
{
PII cur = q.poll();
for (int i = 0; i < 4; ++ i)
{
int x = cur.first + dx[i];
int y = cur.second + dy[i];
if (x >= 0 && x < a && y >= 0 && y < c)
{
if (d[x][y] != -1) continue;
if (g[x][y] == '#') continue;
d[x][y] = d[cur.first][cur.second] + 1;
if (x == tend.first && y == tend.second) return d[x][y];
q.add(new PII(x, y));
}
}
}
return -1;
}
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
t = Integer.parseInt(reader.readLine());
while(t -- > 0)
{
String [] strs = reader.readLine().split(" ");
a = Integer.parseInt(strs[0]);
c = Integer.parseInt(strs[1]);
for (int i = 0; i < a; ++ i)
{
g[i] = reader.readLine().toCharArray();
// System.out.println(g[i]);
for (int j = 0; j < c; ++ j)
{
if (g[i][j] == 'S') start = new PII(i, j);
else if (g[i][j] == 'E') tend = new PII(i, j);
}
}
// System.out.println(start.first + " " + start.second);
int res = bfs();
if (res == -1)
{
writer.write("oop!\n");
writer.flush();
// System.out.println("oop!");
}
else
{
writer.write(res+"\n");
writer.flush();
//System.out.println(res);
}
}
}
}
class PII
{
int first, second;
public PII(int x, int y)
{
this.first = x;
this.second = y;
}
}
Python
import queue
T= int(input())
def dfs(start,end):
dist[start[0]][start[1]]=0
dx,dy=[-1,0,1,0],[0,1,0,-1]
que=[]
que.append(start)
while len(que):
t= que.pop(0)
for i in range(4):
Y,X= t[0]+dx[i],t[1]+dy[i]
#出界
if(X<0 or X>=line or Y<0 or Y>=row):continue
#障碍物
if(g[Y][X]=='#'):continue
#已经走过了
if(dist[Y][X]!=-1):continue
dist[Y][X]= dist[t[0]][t[1]]+1
if(end==[Y,X]):
return dist[Y][X]
que.append([Y,X])
return -1
for i in range((T)):
s = list(map(int, input().split(' ')))
row, line = s[0], s[1]
dist=[[-1]*line for l in range(row)]
start, end = [], []
g=[]
for k in range(row):
g.append(input())
for h in range(len(g)):
for w in range(line):
if(g[h][w]=='S'):
start=[h,w]
if(g[h][w]=='E'):
end=[h,w]
t1= dfs(start,end)
if(t1==-1):
print('oop!')
else:
print(t1)
相关文章
- 献给那些想自建站搭建博客的新人们(实篇)wordpress
- 献给那些想自建站搭建博客的新人们(启篇)
- 献给那些想自建站搭建博客的新人们(实篇)wordpress
- 献给那些想自建站搭建博客的新人们(启篇)
- 献给阿尔吉侬的花束(二刷,迷宫bfs,模板题)
- 献给阿尔吉侬的花束(迷宫bfs)
- 【经验】谈谈办证的那些事,献给那些即将毕业、或孩子上学等朋友
- 献给Python初学者,零基础学习Python能学会吗?
- DayDayUp:五四青年节快乐!献给新一代的演讲—《后浪》—心里有火 眼里有光 ,奔涌吧 后浪
- 学Python什么时候都不晚,献给每一个对现状不满的奋斗者
- cocos2d-x 3.0来做一个简单的游戏教程 win32平台 vs2012 详解献给刚開始学习的人们!
- OpenCms创建站点过程图解——献给OpenCms的刚開始学习的人们
- 摸爬滚打大半年,我是如何从零基础成长为渗透测试工程师的,仅献给同样在奋斗的自己和在看的你
- 【经验】谈谈办证的那些事,献给那些即将毕业、或孩子上学等朋友(转)
- ❤❤算法基础&递归&查找&十大排序算法,献给快要开学的你❤❤
- 《思路决定出路》——毕业后五年决定你的命运——献给所有心怀梦想之人