第一行输入一个数字n(1≤n≤1000)表示公园的边长
接下来会给你一个n*n的公园地图,其中 . 表示公园里的道路,@表示公园的入口,*表示公园的出口,#表示公园内的湖和建筑。牛牛和他的小伙伴们每次只能上下左右移动一格位置。
输入保证公园入口个数m(1≤m≤10000)且所有的入口都能和出口相连。
输出牛牛需要行走的最短距离。
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; }
#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; }
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; } }
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(); } }
#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); } } } } }
//递归超时,动态规划容易写错,还是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;
}
}
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;
}
}
}