[编程题]牛牛游玩记
- 热度指数：840 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
又是晴朗的一天，牛牛的小伙伴们都跑来找牛牛去公园玩。但是牛牛想呆在家里看E3展，不想出去逛公园，可是牛牛又不想鸽掉他的小伙伴们，于是找来了公园的地图，发现公园是由一个边长为n的正方形构成的，公园一共有m个入口，但出口只有一个。公园内有一些湖和建筑，牛牛和他的小伙伴们肯定不能从他们中间穿过，所以只能绕行。牛牛想知道他需要走的最短距离并输出这个最短距离。
输入描述:
第一行输入一个数字n(1≤n≤1000)表示公园的边长
接下来会给你一个n*n的公园地图，其中 . 表示公园里的道路，@表示公园的入口，*表示公园的出口，#表示公园内的湖和建筑。牛牛和他的小伙伴们每次只能上下左右移动一格位置。
输入保证公园入口个数m(1≤m≤10000)且所有的入口都能和出口相连。
输出描述:
输出牛牛需要行走的最短距离。
示例1
输入
10 .@....##@. ......#... ...@..#... ###....... ....##..#. ...####... @...##.... #####..... ..##*####. #.........
输出
16
#include<iostream> #include<vector> #include<queue> using namespace std; int dir[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } }; int main() { int n; cin >> n; vector<vector<char>>park(n, vector<char>(n, 0)); queue<pair<int, int>>que; for (int i = 0; i != n; ++i) for (int j = 0; j != n; ++j) { cin >> park[i][j]; if (park[i][j] == '*') que.push({i*n + j, 0});//将终点位置入队 } while (!que.empty())//广搜到第一个起点就是最短距离 { auto &cur = que.front(); for (int i = 0; i != 4; ++i) { int next_x = cur.first / n + dir[i][0]; int next_y = cur.first%n + dir[i][1]; if (next_x >= 0 && next_x < n&& next_y >= 0 && next_y < n) { if (park[next_x][next_y] == '.') { que.push({next_x*n + next_y, cur.second + 1}); park[next_x][next_y] = 'x';//标记遍历过的点 } else if (park[next_x][next_y] == '@') { cout << cur.second + 1; return 0; } } } que.pop(); } return 0; }
编辑于 2018-08-07 19:27:06
回复(1)
C++ 多源点BFS
#include <bits/stdc++.h>
using namespace std;
int dirs[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
int main() {
int n, endx, endy;
char grid[1002][1002];
cin >> n;
queue<pair<int, int>> q;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> grid[i][j];
if (grid[i][j] == '@') { q.emplace(i, j); grid[i][j] = '#'; }
else if (grid[i][j] == '*') { endx = i; endy = j; }
}
}
int step = 0;
while (!q.empty()) {
int size = q.size();
while (size--) {
auto [x, y] = q.front(); q.pop();
if (x == endx && y == endy) { printf("%d\n", step); return 0; } // 到达终点
for (auto &[dx, dy] : dirs) { // 四个方向遍历
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] != '#') {
q.emplace(nx, ny);
grid[nx][ny] = '#'; // 不再访问
}
}
}
step++; // 路径长度+1
}
return 0;
}
发表于 2022-08-19 22:18:13
回复(0)
BFS，从出口开始计算
import java.awt.Point;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public c***in3 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
char arr [][] = new char[n][n];
char a[] = new char[n];
int p = 0,q = 0;
//构建矩阵，记录出口坐标
for(int i=0;i<n;i++){
String str = sc.nextLine();
a = str.toCharArray();
for(int j=0;j<n;j++){
arr[i][j] = a[j];
if(a[j]=='*'){
p = i;
q = j;
}
}
}
int number = bfs(arr,p,q,n);
System.out.println(number);
}
private static int bfs(char[][] arr, int p, int q, int n) {
//deep用于判断是否走过以及计算步长
int deep[][] = new int[n][n];
for (int k = 0; k < n; k++)
for (int l = 0; l < n; l++)
deep[k][l] = -1;
deep[p][q] = 0;
Queue<Point> queue = new LinkedList<Point>();
queue.offer(new Point(p, q));
int[] tx = { -1, 1, 0, 0 };
int[] ty = { 0, 0, 1, -1 };
while(queue.size()>0){
Point top = queue.poll();
int i = top.x;
int j = top.y;
if(arr[i][j]=='@'){
return deep[i][j];
}
for (int k = 0; k < 4; k++) {
int x = top.x + tx[k];
int y = top.y + ty[k]; //p为当前位置；
if (x >= 0 && x < n && y >= 0 && y < n && arr[x][y] != '#' && deep[x][y] == -1) {
deep[x][y] = deep[top.x][top.y] + 1;
queue.offer(new Point(x, y));
}
}
}
return 0;
}
}
编辑于 2019-05-16 18:41:55
回复(0)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public clas***ain {
static class Point{
int x;
int y;
int steps;
public Point(int x, int y, int steps) {
this.x = x;
this.y = y;
this.steps = steps;
}
}
private static int minStep = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
int n = in.nextInt();
int[][] map = new int[n][n];
int[][] book = new int[n][n];
Queue<Point> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
String s = in.next();
char[] tmp = s.toCharArray();
for (int j = 0; j < n; j++) {
if (tmp[j] == '@') {
map[i][j] = 2;//入口
} else if (tmp[j] == '.') {
map[i][j] = 0;//道路
} else if (tmp[j] == '#') {
map[i][j] = 1;//障碍
} else {
map[i][j] = 3;//出口
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 2) {
book[i][j] = 1;
queue.offer(new Point(i,j,0));
}
}
}
//以下为bfs
int[][] next = {
{0,1},
{1,0},
{0,-1},
{-1,0}
};
while (!queue.isEmpty()){
Point p = queue.poll();
int tx,ty;
for (int i = 0; i < 4; i++) {
tx = p.x + next[i][0];
ty = p.y + next[i][1];
if (tx < 0 || tx > n - 1 || ty < 0 || ty > n - 1){
continue;
}
if (map[tx][ty] == 0 && book[tx][ty] == 0) {
book[tx][ty] = 1;
queue.offer(new Point(tx,ty,p.steps + 1));
}
if (map[tx][ty] == 3) {
minStep = Math.min(p.step***inStep);
break;
}
}
}
System.out.println(minStep + 1);
}
in.close();
}
}
编辑于 2019-05-17 14:29:17
回复(0)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x) for(int i=0;i<(x);i++)
#define in_range(x,a,b) (a<=x && x<b)
struct point{
int x,y,c; //位置x,y 距离出口 c
};
int dxy[2][4]={
{-1,1,0,0},
{0,0,-1,1},
};
int main(){
ios::sync_with_stdio(0); cin.tie(NULL); //cin加速器
int n; cin>>n;
char mp[n][n];
queue<point> q;
rep(i,n)rep(j,n) {
cin>>mp[i][j];
if(mp[i][j]=='*'){
q.emplace(i,j,0);
}
}
while(!q.empty()){
point now = q.front();q.pop();
rep(i,4){ //四个方向
point nxt{now.x+dxy[0][i],now.y+dxy[1][i],now.c+1};
if( in_range(nxt.x,0,n) and in_range(nxt.y,0,n) ){
char c = mp[nxt.x][nxt.y];
if (c=='.'){
q.push(nxt);
mp[nxt.x][nxt.y]='#'; //这里需要注意, 防止push重复的点
}
else if (c=='@'){
cout<<nxt.c<<endl;
exit(0);
}
}
}
}
} 哪里不容易看懂请留言
编辑于 2020-03-28 13:13:16
回复(1)
def move(bmap,N):
direct = [(1,0), (-1,0), (0,1), (0,-1)]
for i in range(N):
for j in range(N):
if bmap[i][j] == '*':
end_x,end_y = i,j
step = 0
stack = []
bfs = [[False for raw in range(N)] for col in range(N)]
bfs[end_x][end_y] == True
stack.append((end_x, end_y))
while stack:
step += 1
for k in range(len(stack)):
px,py = stack.pop(0)
for dx, dy in direct:
nx = px + dx
ny = py + dy
if nx >=0 and nx < N and ny >=0 and ny < N and not bfs[nx][ny] and bmap[nx][ny] != '#':
if bmap[nx][ny] == '@':
return step
bfs[nx][ny] = True
stack.append((nx,ny))
return -1
if __name__=='__main__':
N = int(raw_input())
bmap = []
for i in range(N):
bmap.append([ch for ch in raw_input().split()[0]])
print (move(bmap,N))
direct = [(1,0), (-1,0), (0,1), (0,-1)]
for i in range(N):
for j in range(N):
if bmap[i][j] == '*':
end_x,end_y = i,j
step = 0
stack = []
bfs = [[False for raw in range(N)] for col in range(N)]
bfs[end_x][end_y] == True
stack.append((end_x, end_y))
while stack:
step += 1
for k in range(len(stack)):
px,py = stack.pop(0)
for dx, dy in direct:
nx = px + dx
ny = py + dy
if nx >=0 and nx < N and ny >=0 and ny < N and not bfs[nx][ny] and bmap[nx][ny] != '#':
if bmap[nx][ny] == '@':
return step
bfs[nx][ny] = True
stack.append((nx,ny))
return -1
if __name__=='__main__':
N = int(raw_input())
bmap = []
for i in range(N):
bmap.append([ch for ch in raw_input().split()[0]])
print (move(bmap,N))
发表于 2018-07-11 14:28:42
回复(0)
#include<iostream>
#include<vector>
#include<queue>
void func(std::vector<std::vector<long>> &data, std::vector<std::vector<char>> &map,long pos_x, long pos_y)
{
std::queue<std::pair<long, long>> q;
q.push(std::pair<long, long>(pos_x, pos_y));
while (!q.empty())
{
std::pair<long, long> pos = q.front();
if (pos.first + 1 < map.size())
{
if (map[pos.first + 1][pos.second] != '#')
{
if (data[pos.first + 1][pos.second] > 1 + data[pos.first][pos.second])
{
data[pos.first + 1][pos.second] = 1 + data[pos.first][pos.second];
q.push(std::pair<long, long>(pos.first + 1, pos.second));
}
}
}
if (pos.first - 1 >=0)
{
if (map[pos.first - 1][pos.second] != '#')
{
if (data[pos.first - 1][pos.second] > 1 + data[pos.first][pos.second])
{
data[pos.first - 1][pos.second] = 1 +data[pos.first][pos.second];
q.push(std::pair<long, long>(pos.first - 1, pos.second));
}
}
}
if (pos.second + 1 < map.size())
{
if (map[pos.first][pos.second+1] != '#')
{
if (data[pos.first][pos.second+1] > 1 + data[pos.first][pos.second])
{
data[pos.first][pos.second+1] = 1 + data[pos.first][pos.second];
q.push(std::pair<long, long>(pos.first, pos.second+1));
}
}
}
if (pos.second -1 >= 0)
{
if (map[pos.first][pos.second-1] != '#')
{
if (data[pos.first][pos.second-1] > 1 + data[pos.first][pos.second])
{
data[pos.first][pos.second-1] = 1 + data[pos.first][pos.second];
q.push(std::pair<long, long>(pos.first, pos.second-1));
}
}
}
q.pop();
}
}
int main()
{
long n;
std::cin >> n;
char c;
std::vector<char> map1(n);
std::vector<std::vector<char>> map(n, map1);
std::vector<long> data1(n, 1000000);
std::vector < std::vector<long>> data(n, data1);
long pos_x, pos_y;
long min_dis=1000000;
for(int i=0;i<n;i++)
for (int j = 0; j < n; j++)
{
std::cin >> c;
map[i][j] = c;
if (c == '*')
{
pos_x = i;
pos_y = j;
data[i][j]=0;
}
}
func(data,map,pos_x,pos_y);
for(int i=0;i<n;i++)
for (int j = 0; j < n; j++)
{
if (map[i][j] == '@')
if (min_dis > data[i][j])
min_dis = data[i][j];
}
std::cout << min_dis;
return 0;
}
#include<vector>
#include<queue>
void func(std::vector<std::vector<long>> &data, std::vector<std::vector<char>> &map,long pos_x, long pos_y)
{
std::queue<std::pair<long, long>> q;
q.push(std::pair<long, long>(pos_x, pos_y));
while (!q.empty())
{
std::pair<long, long> pos = q.front();
if (pos.first + 1 < map.size())
{
if (map[pos.first + 1][pos.second] != '#')
{
if (data[pos.first + 1][pos.second] > 1 + data[pos.first][pos.second])
{
data[pos.first + 1][pos.second] = 1 + data[pos.first][pos.second];
q.push(std::pair<long, long>(pos.first + 1, pos.second));
}
}
}
if (pos.first - 1 >=0)
{
if (map[pos.first - 1][pos.second] != '#')
{
if (data[pos.first - 1][pos.second] > 1 + data[pos.first][pos.second])
{
data[pos.first - 1][pos.second] = 1 +data[pos.first][pos.second];
q.push(std::pair<long, long>(pos.first - 1, pos.second));
}
}
}
if (pos.second + 1 < map.size())
{
if (map[pos.first][pos.second+1] != '#')
{
if (data[pos.first][pos.second+1] > 1 + data[pos.first][pos.second])
{
data[pos.first][pos.second+1] = 1 + data[pos.first][pos.second];
q.push(std::pair<long, long>(pos.first, pos.second+1));
}
}
}
if (pos.second -1 >= 0)
{
if (map[pos.first][pos.second-1] != '#')
{
if (data[pos.first][pos.second-1] > 1 + data[pos.first][pos.second])
{
data[pos.first][pos.second-1] = 1 + data[pos.first][pos.second];
q.push(std::pair<long, long>(pos.first, pos.second-1));
}
}
}
q.pop();
}
}
int main()
{
long n;
std::cin >> n;
char c;
std::vector<char> map1(n);
std::vector<std::vector<char>> map(n, map1);
std::vector<long> data1(n, 1000000);
std::vector < std::vector<long>> data(n, data1);
long pos_x, pos_y;
long min_dis=1000000;
for(int i=0;i<n;i++)
for (int j = 0; j < n; j++)
{
std::cin >> c;
map[i][j] = c;
if (c == '*')
{
pos_x = i;
pos_y = j;
data[i][j]=0;
}
}
func(data,map,pos_x,pos_y);
for(int i=0;i<n;i++)
for (int j = 0; j < n; j++)
{
if (map[i][j] == '@')
if (min_dis > data[i][j])
min_dis = data[i][j];
}
std::cout << min_dis;
return 0;
}
发表于 2018-07-04 16:16:46
回复(0)
//递归超时，动态规划容易写错，还是BFS好使
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int main()
{
int n;
while(cin>>n)
{
vector<vector<char>> co(n,vector<char>(n));
int ox,oy;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>co[i][j];
if(co[i][j]=='*')
{ ox=i;oy=j;}
}
}
queue<pair<int,int>> tp;
tp.push(pair<int,int>(ox,oy));
int count=0;
int cnt;
int num=1;
bool find=false;
while(!tp.empty()&&!find)
{
cnt=num;
num=0;
while(cnt--&&!find)
{
pair<int,int> cur=tp.front();
tp.pop();
int xt,yt;
for(int i=0;i<4;i++)
{
xt=cur.first+dir[i][0];
yt=cur.second+dir[i][1];
if(xt<0||yt<0||xt>=n||yt>=n||co[xt][yt]=='-'||co[xt][yt]=='#')
continue;
if(co[xt][yt]=='@')
{
find=true;
break;
}
else if(co[xt][yt]=='.')
{
tp.push(pair<int,int>(xt,yt));
co[xt][yt]='-';
num++;
}
}
}
count++;
}
cout<<count<<endl;
}
}
发表于 2018-06-30 08:47:43
回复(0)
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String s1 = scanner.nextLine();
int n = Integer.parseInt(s1);
int shortest=0;
int x=0; //出口点x轴位置
int y=0; //出口点y轴位置
//将路径以字符串形式存储到数组中
String[][] arrstr = new String[n][n];
for (int i = 0; i < n; i++) {
String s = scanner.nextLine();
char[] chars = s.toCharArray();
for (int j = 0; j < chars.length; j++) {
Character aChar = chars[j];
String f=aChar.toString();
if(f.equals("*")){ //找到出口点，进行广搜。
x=i;
y=j;
}
arrstr[i][j]=f;
}
}
String[][] arrflag = new String[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arrflag[i][j] = "NO";
}
}
//广搜，由广搜性质，碰到第一个@就停止， 输出长度
List<Node> nodeList = new LinkedList<>(); //存储已经找到的点
String s = arrstr[x][y]; //起点
Node startNode=new Node();
startNode.setDis(0);
startNode.setX(x);
startNode.setY(y);
nodeList.add(startNode);
while (!nodeList.isEmpty()) {
//取出链表中第一个节点
Node firstNode = nodeList.remove(0);
int axisx=firstNode.getX(); //x轴
int axisy=firstNode.getY(); //y轴
int dis=firstNode.getDis(); //距离
if (axisx - 1 >= 0) { //上
String flagup = arrflag[axisx - 1][axisy]; //标记
String symbol=arrstr[axisx -1][axisy];//符号
if (flagup.equals("NO")&&!symbol.equals("#")) {
if (symbol.equals("@")) {
shortest=dis+1; //最终的距离
break;
}
Node nodeUp=new Node();
nodeUp.setX(axisx-1);
nodeUp.setY(axisy);
nodeUp.setDis(dis+1);
arrflag[axisx -1][axisy]="YES";
nodeList.add(nodeUp);
}
}
if (axisx + 1 < n) { //下
String flagup = arrflag[axisx + 1][axisy]; //标记
String symbol=arrstr[axisx +1][axisy];//符号
if (flagup.equals("NO")&&!symbol.equals("#")) {
if (symbol.equals("@")) {
shortest=dis+1; //最终的距离
break;
}
Node nodeDown=new Node();
nodeDown.setX(axisx+1);
nodeDown.setY(axisy);
nodeDown.setDis(dis+1);
arrflag[axisx +1][axisy]="YES";
nodeList.add(nodeDown);
}
}
if (axisy-1 >= 0) { //左
String flagup = arrflag[axisx][axisy-1]; //标记
String symbol=arrstr[axisx][axisy-1];//符号
if (flagup.equals("NO")&&!symbol.equals("#")) {
if (symbol.equals("@")) {
shortest=dis+1; //最终的距离
break;
}
Node nodeLeft=new Node();
nodeLeft.setX(axisx);
nodeLeft.setY(axisy-1);
nodeLeft.setDis(dis+1);
arrflag[axisx][axisy-1]="YES";
nodeList.add(nodeLeft);
}
}
if (axisy + 1 < n) { //右
String flagup = arrflag[axisx][axisy+1]; //标记
String symbol=arrstr[axisx][axisy+1];//符号
if (flagup.equals("NO")&&!symbol.equals("#")) {
if (symbol.equals("@")) {
shortest=dis+1; //最终的距离
break;
}
Node nodeRight=new Node();
nodeRight.setX(axisx);
nodeRight.setY(axisy+1);
nodeRight.setDis(dis+1);
arrflag[axisx][axisy+1]="YES";
nodeList.add(nodeRight);
}
}
}
System.out.println(shortest);
}
static class Node{
int x;
int y;
int dis;
public int getX() {
return x;
}
public int getDis() {
return dis;
}
public void setDis(int dis) {
this.dis = dis;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
}
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String s1 = scanner.nextLine();
int n = Integer.parseInt(s1);
int shortest=0;
int x=0; //出口点x轴位置
int y=0; //出口点y轴位置
//将路径以字符串形式存储到数组中
String[][] arrstr = new String[n][n];
for (int i = 0; i < n; i++) {
String s = scanner.nextLine();
char[] chars = s.toCharArray();
for (int j = 0; j < chars.length; j++) {
Character aChar = chars[j];
String f=aChar.toString();
if(f.equals("*")){ //找到出口点，进行广搜。
x=i;
y=j;
}
arrstr[i][j]=f;
}
}
String[][] arrflag = new String[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arrflag[i][j] = "NO";
}
}
//广搜，由广搜性质，碰到第一个@就停止， 输出长度
List<Node> nodeList = new LinkedList<>(); //存储已经找到的点
String s = arrstr[x][y]; //起点
Node startNode=new Node();
startNode.setDis(0);
startNode.setX(x);
startNode.setY(y);
nodeList.add(startNode);
while (!nodeList.isEmpty()) {
//取出链表中第一个节点
Node firstNode = nodeList.remove(0);
int axisx=firstNode.getX(); //x轴
int axisy=firstNode.getY(); //y轴
int dis=firstNode.getDis(); //距离
if (axisx - 1 >= 0) { //上
String flagup = arrflag[axisx - 1][axisy]; //标记
String symbol=arrstr[axisx -1][axisy];//符号
if (flagup.equals("NO")&&!symbol.equals("#")) {
if (symbol.equals("@")) {
shortest=dis+1; //最终的距离
break;
}
Node nodeUp=new Node();
nodeUp.setX(axisx-1);
nodeUp.setY(axisy);
nodeUp.setDis(dis+1);
arrflag[axisx -1][axisy]="YES";
nodeList.add(nodeUp);
}
}
if (axisx + 1 < n) { //下
String flagup = arrflag[axisx + 1][axisy]; //标记
String symbol=arrstr[axisx +1][axisy];//符号
if (flagup.equals("NO")&&!symbol.equals("#")) {
if (symbol.equals("@")) {
shortest=dis+1; //最终的距离
break;
}
Node nodeDown=new Node();
nodeDown.setX(axisx+1);
nodeDown.setY(axisy);
nodeDown.setDis(dis+1);
arrflag[axisx +1][axisy]="YES";
nodeList.add(nodeDown);
}
}
if (axisy-1 >= 0) { //左
String flagup = arrflag[axisx][axisy-1]; //标记
String symbol=arrstr[axisx][axisy-1];//符号
if (flagup.equals("NO")&&!symbol.equals("#")) {
if (symbol.equals("@")) {
shortest=dis+1; //最终的距离
break;
}
Node nodeLeft=new Node();
nodeLeft.setX(axisx);
nodeLeft.setY(axisy-1);
nodeLeft.setDis(dis+1);
arrflag[axisx][axisy-1]="YES";
nodeList.add(nodeLeft);
}
}
if (axisy + 1 < n) { //右
String flagup = arrflag[axisx][axisy+1]; //标记
String symbol=arrstr[axisx][axisy+1];//符号
if (flagup.equals("NO")&&!symbol.equals("#")) {
if (symbol.equals("@")) {
shortest=dis+1; //最终的距离
break;
}
Node nodeRight=new Node();
nodeRight.setX(axisx);
nodeRight.setY(axisy+1);
nodeRight.setDis(dis+1);
arrflag[axisx][axisy+1]="YES";
nodeList.add(nodeRight);
}
}
}
System.out.println(shortest);
}
static class Node{
int x;
int y;
int dis;
public int getX() {
return x;
}
public int getDis() {
return dis;
}
public void setDis(int dis) {
this.dis = dis;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
}
发表于 2018-06-27 20:19:03
回复(0)
importjava.util.ArrayList;
importjava.util.LinkedList;
importjava.util.Scanner;
classPoint {
intx;
inty;
Point(intx,inty){
this.x=x;
this.y=y;
}
}
///动态规划
public class Main {
publicstaticvoidmain(String[] args) {
Scanner sc=newScanner(System.in);
intn=sc.nextInt();
char[][] maps=newchar[n][n]; // 构建字符串数组，记录每个位置的符号
ArrayList<Point> ins=newArrayList<>();
Point end=null;
for(inti=0;i<n;i++){
String temp=sc.next();
for(intj=0;j<n;j++){
maps[i][j]=temp.charAt(j);
if(maps[i][j]=='@') ins.add(newPoint(i,j));//用list记录所有入口的坐标
elseif(maps[i][j]=='*') end=newPoint(i,j); //记录出口的坐标
}
}
int[][] res=newint[n][n];//构建结果集数组，每个点的值为，以(i,j)作为出发点到出口要走的距离
boolean[][] flag=newboolean[n][n];
find(res,end,maps,flag);//调用find方法，往res数组填数据
intresult=Integer.MAX_VALUE;//取出之前记录的入口坐标，看看从哪个入口出发，走到出口的距离最近
for(inti=0;i<ins.size();i++){
Point point=ins.get(i);
if(res[point.x][point.y]<result) result=res[point.x][point.y];
}
System.out.println(result);
}
publicstaticvoidfind(int[][] res,Point end,char[][] maps, boolean[][] flag){
LinkedList<Point> queue=newLinkedList<>(); //bfs思想
res[end.x][end.y]=0; //从出口开始，不断向外遍历，记录每个点到出口的距离
queue.offer(end);
while(!queue.isEmpty()){
Point dot=queue.poll();
intx=dot.x;
inty=dot.y;
if(calDistance(res,x+1,y,maps,flag,res[x][y]))queue.offer(newPoint(x+1,y));//进行判断，符合条件的点加入queue，下一步可以从该点向别的点走
if(calDistance(res,x-1,y,maps,flag,res[x][y]))queue.offer(newPoint(x-1,y));
if(calDistance(res,x,y+1,maps,flag,res[x][y]))queue.offer(newPoint(x,y+1));
if(calDistance(res,x,y-1,maps,flag,res[x][y]))queue.offer(newPoint(x,y-1));
}
}
privatestaticbooleancalDistance(int[][] res, inti, intj, char[][] maps, boolean[][] flag,intval) {
if(i<0||i>=res.length||j<0||j>=res.length||flag[i][j]==true||maps[i][j]=='#')returnfalse;
//不超过公园的坐标范围，以及该点没有障碍物，并且没有被走过
else{
res[i][j]=val+1; //该点到出口的距离为，前一个点的距离+1
flag[i][j]=true;
return true;
}
}
}
编辑于 2018-07-04 21:18:01
回复(2)
问题信息
通过挑战的用户
-
2022-11-01 08:56:09
-
2022-09-09 13:06:03
-
2022-08-19 17:53:38
-
2022-07-07 13:06:28
-
2022-03-20 09:27:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
