AB20. 走迷宫
描述
给定一个输入描述
第一行输入两个整数第二行输入四个整数
接下来的
保证起点不存在障碍物。
输出描述
输出一行一个整数，表示从示例1
输入:
5 5 1 1 5 5 ..... ****. ..... **.** .....
输出:
12
示例2
输入:
5 5 1 1 4 5 ..... ****. ..... **.** .....
输出:
-1
示例3
输入:
5 5 1 1 5 5 ..... ****. ..... ***** .....
输出:
-1
AB20. 走迷宫
描述
给定一个输入描述
第一行输入两个整数输出描述
输出一行一个整数，表示从示例1
输入:
5 5 1 1 5 5 ..... ****. ..... **.** .....
输出:
12
示例2
输入:
5 5 1 1 4 5 ..... ****. ..... **.** .....
输出:
-1
示例3
输入:
5 5 1 1 5 5 ..... ****. ..... ***** .....
输出:
-1
C++ 解法, 执行用时: 25ms, 内存消耗: 2312KB, 提交时间: 2022-04-24
#include<stdio.h>
#include <queue>
#include <iostream>
using namespace std;
char a[1020][1020];
bool visit[1000][1000];
int m,n,x1,y1,x2,y2;
struct dui{
int x;
int y;
int l;
}tt,temp;
queue<dui> q;
void bfs()
{
temp.x=x1;
temp.y=y1;
temp.l=0;
visit[x1][y1]=1;
q.push(temp);
// int num=-1;
// printf("%d%d\n",temp.x,temp.y);
// printf("%d",q.empty());
while(!q.empty())
{
temp=q.front();
q.pop();
int tempx=temp.x,tempy=temp.y,templ=temp.l;
visit[tempx][tempy]=1;
// printf("%d%d\n",tempx,tempy);
if(tempx==x2&&tempy==y2)
{
printf("%d\n",templ);
return;
}
if(a[x2][y2]=='*')
{
break;
}
if(tempx-1>=0&&a[tempx-1][tempy]=='.')
{
struct dui tmp;
tmp.x=tempx-1;
tmp.y=tempy;
tmp.l=templ+1;
if(visit[tmp.x][tmp.y]==0)
{
visit[tmp.x][tmp.y]=1;
q.push(tmp);
}
}
if(tempx+1<m&&a[tempx+1][tempy]=='.')
{
struct dui tmp;
tmp.x=tempx+1;
tmp.y=tempy;
tmp.l=templ+1;
if(visit[tmp.x][tmp.y]==0)
{
visit[tmp.x][tmp.y]=1;
q.push(tmp);
}
}
if(tempy-1>=0&&a[tempx][tempy-1]=='.')
{
struct dui tmp;
tmp.x=tempx;
tmp.y=tempy-1;
tmp.l=templ+1;
if(visit[tmp.x][tmp.y]==0)
{
visit[tmp.x][tmp.y]=1;
q.push(tmp);
}
}
if(tempy+1<n&&a[tempx][tempy+1]=='.')
{
// printf("hh");
struct dui tmp;
tmp.x=tempx;
tmp.y=tempy+1;
tmp.l=templ+1;
if(visit[tmp.x][tmp.y]==0)
{
visit[tmp.x][tmp.y]=1;
q.push(tmp);
}
}
// printf("%d",q.empty());
}
printf("-1\n");
}
int main ()
{
scanf("%d%d",&m,&n);
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for(int i=0;i<m;i++)
{
scanf("%s",a[i]);
// printf("%s\n",a[i]);
}
x1--;y1--;x2--;y2--;
bfs();
return 0;
}
C++ 解法, 执行用时: 26ms, 内存消耗: 1420KB, 提交时间: 2022-07-21
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
static const auto io_sync_off = [](){
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
return nullptr;
}();
int main()
{
int n,m;
cin>>n>>m;
int xs,ys,xt,yt;
cin>>xs>>ys>>xt>>yt;
xs--,ys--,xt--,yt--;
vector<string>a(n);
for(int i=0;i<n;i++)
cin>>a[i];
queue<pair<int,int>>q;
int res=0;
q.push({xs,ys});
const vector<vector<int>> movelist{{0,-1},{0,1},{-1,0},{1,0}};
while(!q.empty())
{
int l=q.size();
for(int i=0;i<l;i++)
{
auto r=q.front();
q.pop();
int x = r.first;
int y = r.second;
if(x==xt&&y==yt)
{
cout<<res;
return 0;
}
for(int j=0;j<4;j++)
{
int nx=x+movelist[j][0];
int ny=y+movelist[j][1];
if(nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]=='.')
{
a[nx][ny]='*';
q.push({nx,ny});
}
}
}
res++;
}
cout<<-1;
return 0;
}
C++ 解法, 执行用时: 26ms, 内存消耗: 4364KB, 提交时间: 2022-07-06
#include<bits/stdc++.h>
#include<queue>
using namespace std;
typedef pair<int,int> Pt;
struct point{
int x,y;
};
queue<Pt> q;
queue<point> Q;
int mp[1002][1002]={0};
int isorder[1001][1001]={0};
int a=0;
int dfs(int i,int j,int k,int l,int a){
int b1=99999999,b2=99999999,b3=99999999,b4=99999999;
if(i==k&&j==l) return a;
mp[i][j]=1;//printf("%d,%d=%d ",i,j,a);
if(mp[i][j+1]==0)b4=dfs(i,j+1,k,l,a+1);
if(mp[i+1][j]==0)b3=dfs(i+1,j,k,l,a+1);
if(mp[i-1][j]==0)b1=dfs(i-1,j,k,l,a+1);
if(mp[i][j-1]==0)b2=dfs(i,j-1,k,l,a+1);
a=min(min(b1,b2),min(b3,b4));//printf("%d,%d=%d ",i,j,a);
return a;
}
int bfs(int b1,int b2,int k,int l){
//pair<int,int>q1(b1,b2);//point与pair内存差不多
point q1={b1,b2};
int i,j,ci=0,p,z;
//Pt q2;
//q.push(q1);
point q2;
Q.push(q1);mp[b1][b2]=1;
while(!Q.empty()){p=Q.size();
for(z=0;z<p;z++){
q2=Q.front();Q.pop();
i=q2.x;j=q2.y;//printf("%d,%d=%d ",i,j,ci);
if(i==k&&j==l) return ci;
if(mp[i][j+1]==0){Q.push(point{i,j+1});mp[i][j+1]=1;}
if(mp[i+1][j]==0){Q.push(point{i+1,j});mp[i+1][j]=1;}
if(mp[i-1][j]==0){Q.push(point{i-1,j});mp[i-1][j]=1;}
if(mp[i][j-1]==0){Q.push(point{i,j-1});mp[i][j-1]=1;}
}ci+=1;
}
return -1;
}
int bfs1(int b1,int b2,int k,int l){
//pair<int,int>q1(b1,b2);//point与pair内存差不多
point q1={b1,b2};
int i,j,ci=0,p,z;
//Pt q2;
//q.push(q1);
point q2;
Q.push(q1);
while(!Q.empty()){p=Q.size();
if(p>10000000)return Q.front().x;
printf("%d ",ci);if(ci%15==0)printf("\n");
for(z=0;z<p;z++){
q2=Q.front();Q.pop();
i=q2.x;j=q2.y;if(ci>50)printf("%d,%d=%d ",i,j,ci);
//if(ci==27)printf("$%d$ ",Q.size());
if(i==k&&j==l) return ci;
mp[i][j]=1;
if(mp[i][j+1]==0)Q.push(point{i,j+1});
if(mp[i+1][j]==0)Q.push(point{i+1,j});
if(mp[i-1][j]==0)Q.push(point{i-1,j});
if(mp[i][j-1]==0)Q.push(point{i,j-1});
}ci+=1;if(ci>50)printf("\n");
}
return -1;
}
int main(){
int n,m;
int x1,x2,y1,y2,x,y;
int i,j,k;char ch[1002];
cin>>n>>m;
cin>>x1>>y1>>x2>>y2;
for(j=0;j<m+2;j++) {//初始化mp数组最外一圈为1注意m!=n
mp[0][j]=mp[n+1][j]=1;
}
for(j=0;j<n+2;j++) {
mp[j][0]=mp[j][m+1]=1;
}
for(i=1;i<n+1;i++){
scanf("%s",&ch);
//printf("%s\n",ch);
for(j=1;j<m+1;j++){
//scanf("%c",&ch);
if(ch[j-1]=='*'){
mp[i][j]=1;
}
}//scanf("%c\n",&ch);
}
/*
for(i=0;i<n+2;i++){
for(j=0;j<m+2;j++){
cout<<mp[i][j];
}cout<<endl;
}//*/
if(n<1000)a=bfs(x1,y1,x2,y2);
else{a=bfs(x1,y1,x2,y2);
for(i=0;i<n+2;i++){
for(j=0;j<m+2;j++){
cout<<mp[i][j];
}cout<<endl;
}}
if(a==99999999)a=-1;
cout<<a;
return 0;
}
C++ 解法, 执行用时: 27ms, 内存消耗: 3392KB, 提交时间: 2022-06-10
#include<stdio.h>
#include <queue>
#include <iostream>
using namespace std;
char a[1020][1020];
bool visit[1000][1000];
int m, n, x1, y1, x2, y2;
struct dui {
int x;
int y;
int l;
} tt, temp;
queue<dui> q;
void bfs() {
temp.x = x1;
temp.y = y1;
temp.l = 0;
visit[x1][y1] = 1;
q.push(temp);
// int num=-1;
// printf("%d%d\n",temp.x,temp.y);
// printf("%d",q.empty());
while (!q.empty()) {
temp = q.front();
q.pop();
int tempx = temp.x, tempy = temp.y, templ = temp.l;
visit[tempx][tempy] = 1;
// printf("%d%d\n",tempx,tempy);
if (tempx == x2 && tempy == y2) {
printf("%d\n", templ);
return;
}
if (a[x2][y2] == '*') {
break;
}
if (tempx - 1 >= 0 && a[tempx - 1][tempy] == '.') {
struct dui tmp;
tmp.x = tempx - 1;
tmp.y = tempy;
tmp.l = templ + 1;
if (visit[tmp.x][tmp.y] == 0) {
visit[tmp.x][tmp.y] = 1;
q.push(tmp);
}
}
if (tempx + 1 < m && a[tempx + 1][tempy] == '.') {
struct dui tmp;
tmp.x = tempx + 1;
tmp.y = tempy;
tmp.l = templ + 1;
if (visit[tmp.x][tmp.y] == 0) {
visit[tmp.x][tmp.y] = 1;
q.push(tmp);
}
}
if (tempy - 1 >= 0 && a[tempx][tempy - 1] == '.') {
struct dui tmp;
tmp.x = tempx;
tmp.y = tempy - 1;
tmp.l = templ + 1;
if (visit[tmp.x][tmp.y] == 0) {
visit[tmp.x][tmp.y] = 1;
q.push(tmp);
}
}
if (tempy + 1 < n && a[tempx][tempy + 1] == '.') {
// printf("hh");
struct dui tmp;
tmp.x = tempx;
tmp.y = tempy + 1;
tmp.l = templ + 1;
if (visit[tmp.x][tmp.y] == 0) {
visit[tmp.x][tmp.y] = 1;
q.push(tmp);
}
}
// printf("%d",q.empty());
}
printf("-1\n");
}
int main () {
scanf("%d%d", &m, &n);
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
for (int i = 0; i < m; i++) {
scanf("%s", a[i]);
// printf("%s\n",a[i]);
}
x1--;
y1--;
x2--;
y2--;
bfs();
return 0;
}
C++ 解法, 执行用时: 32ms, 内存消耗: 3336KB, 提交时间: 2022-04-27
#include <bits/stdc++.h>
using namespace std;
#define maxn 1002
#define P(a,b,c) make_pair(make_pair(a,b),c)
#define INF 0x3f3f3f3f
int n,m;
int xs,xe,ys,ye;
char maps[maxn][maxn];
int a[4][2]={1,0,-1,0,0,1,0,-1};
bool vis[maxn][maxn];
int bfs()
{
memset(vis, 0, sizeof vis);
queue<pair<pair<int,int>, int> >q;
q.push(P(xs,ys,0));
vis[xs][ys]=true;
while(!q.empty())
{
pair< pair<int,int>,int> tmp= q.front();
q.pop();
int x,y;
for(int i=0;i<4;i++)
{
x = tmp.first.first +a[i][0];
y = tmp.first.second + a[i][1];
if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]==false&&maps[x][y]!='*')
{
vis[x][y]=true;
if(x==xe &&y ==ye)return tmp.second+1;
q.push(P(x,y, tmp.second+1));
}
}
}
return -1;
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%d%d%d%d",&xs,&ys,&xe,&ye);
xs--;
ys--;
xe--;
ye--;
for(int i =0;i<n;i++)
{
scanf("%s",maps[i]);
}
int ans =bfs();
printf("%d\n",ans);
return 0;
}