nyist 58 最少步数

最少步数

时间限制：3000 ms | 内存限制：65535 KB

难度：4

描述

这有一个迷宫，有0~8行和0~8列：

1,1,1,1,1,1,1,1,1 1,0,0,1,0,0,1,0,1 1,0,0,1,1,0,0,0,1 1,0,1,0,1,1,0,1,1 1,0,0,0,0,1,0,0,1 1,1,0,1,0,1,0,0,1 1,1,0,1,0,1,0,0,1 1,1,0,1,0,0,0,0,1 1,1,1,1,1,1,1,1,1

0表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

输入

第一行输入一个整数n（0<n<=100），表示有n组测试数据; 随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。

输出

输出最少走几步。

样例输入

2
3 1  5 7
3 1  6 7

样例输出

12
11

///Memory Limit Exceeded

#include <iostream>

#include <queue>

using namespace std;

struct node { int x, y,step; };

struct node s,e;

int dd[4][2]={-1,0,1,0,0,-1,0,1},n,ans;

int g[9][9]={

1,1,1,1,1,1,1,1,1,

1,0,0,1,0,0,1,0,1,

1,0,0,1,1,0,0,0,1,

1,0,1,0,1,1,0,1,1,

1,0,0,0,0,1,0,0,1,

1,1,0,1,0,1,0,0,1,

1,1,0,1,0,0,0,0,1,

1,1,1,1,1,1,1,1,1

}; queue <node> q;

void bfs()

{ node t,t2;

while (! q.empty() ) q.pop();

q.push(s);

while ( !q.empty())

{ t=q.front();

q.pop();

if (t.x==e.x && t.y==e.y) { ans=t.step; return ; }

for (int i=0; i<4; i++) { t2.x=t.x+dd[i][0]; t2.y=t.y+dd[i][1]; t2.step=t.step+1;

if ( g[t2.x][t2.y]==0 ) q.push(t2);

}

int main(int argc, char *argv[])

{

cin>>n;

while (n--)

{ cin>>s.x>>s.y>>e.x>>e.y;

s.step=0;

ans=0;

bfs();

cout<<ans<<endl;

}

return 0;

}

*******************************************************************************************************

//ACCept 时间 2384 内存 58352

#include <iostream>

#include <queue>

#define N 9

#define M 9

using namespace std;

int map[N][M]= {

1,1,1,1,1,1,1,1,1,

1,0,0,1,0,0,1,0,1,

1,0,0,1,1,0,0,0,1,

1,0,1,0,1,1,0,1,1,

1,0,0,0,0,1,0,0,1,

1,1,0,1,0,1,0,0,1,

1,1,0,1,0,0,0,0,1,

1,1,1,1,1,1,1,1,1, };

int d[4][2]={-1,0,0,1,1,0,0,-1 };

struct point {

int x,y,step; //三个属性

}s,e;

queue <point> my;

int BFS(point s) {

int i,x,y;

point t,temp;

while (!my.empty()) my.pop(); //每次都清空白

my.push(s);

while (!my.empty())

{

t=my.front();

my.pop();

for (i=0; i<4; i++)

{ x=t.x+d[i][0];

y=t.y+d[i][1];

if (x==e.x&& y==e.y) return t.step+1;

if (x>=0 && x<N && y>=0 && y<M && map[x][y]==0)

{ temp.x=x;

temp.y=y;

temp.step=t.step+1;

my.push(temp); //当前的

}

int main()

{

int n,x0,y0,ans;

cin>>n;

while (n--)

{ cin>>s.x>>s.y>>e.x>>e.y;

s.step=0;

if (s.x==e.x && s.y==e.y) ans=0;

else ans=BFS(s); // bfs(point s)

cout<<ans<<endl;

}

return 0;

}

*************************************************************

Accept 时间 0 内存 232

#include <iostream>
#include<string.h>
using namespace std;
int used[10][10];
int n,a,b,c,d,ans;
int dd[4][2]={ 0,-1,0,1,-1,0,1,0};
int g[9][9]={
1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,1,0,1,
1,0,0,1,1,0,0,0,1,
1,0,1,0,1,1,0,1,1,
1,0,0,0,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,0,0,0,1,
1,1,1,1,1,1,1,1,1
};

void dfs(int sx,int sy,int cur )
{ int x,y,i ;

if(sx==c && sy==d)
{ if(ans>cur) ans=cur; return; }
for(i=0; i<4; i++)
{ x=sx+dd[i][0]; y=sy+dd[i][1];
if( g[x][y]==0 && used[x][y]==0)
{ used[x][y]=1 ;dfs(x,y,cur+1); used[x][y]=0 ; }
}
}

int main( )
{ cin>>n;
while(n--)
{ memset(used,0,sizeof(used));
cin>>a>>b>>c>>d ; ans=100 ; dfs(a,b,0);
cout<<ans<<endl ;
}

}

*************************************************************

Accept 时间 8 内存 232

#include <iostream>
#include<string.h>
using namespace std;
int n,a,b,c,d,ans;
int dd[4][2]={ 0,-1,0,1,-1,0,1,0};
int g[9][9]={
1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,1,0,1,
1,0,0,1,1,0,0,0,1,
1,0,1,0,1,1,0,1,1,
1,0,0,0,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,0,0,0,1,
1,1,1,1,1,1,1,1,1
};

void dfs(int sx,int sy,int cur )
{ int x,y,i ;
if(sx==c && sy==d)
{ if(ans>cur) ans=cur; return; }
for(i=0; i<4; i++)
{ x=sx+dd[i][0]; y=sy+dd[i][1];
if( g[x][y]==0)
{ g[x][y]=1 ;dfs(x,y,cur+1); g[x][y]=0 ; }
}
}

int main( )
{ cin>>n;
while(n--)
{
cin>>a>>b>>c>>d ; ans=100 ; dfs(a,b,0);
cout<<ans<<endl ;
}

}

*************************************************************

Accept 时间 0 内存 308

#include <cstring>

#include <iostream>

#include <queue>

using namespace std;

int ans;

int g[9][9]= {

1,1,1,1,1,1,1,1,1,

1,0,0,1,0,0,1,0,1,

1,0,0,1,1,0,0,0,1,

1,0,1,0,1,1,0,1,1,

1,0,0,0,0,1,0,0,1,

1,1,0,1,0,1,0,0,1,

1,1,0,1,0,0,0,0,1,

1,1,1,1,1,1,1,1,1,

};

int dd[4][2]={-1,0,0,1,1,0,0,-1 };

int bz[10][10];

struct node{

int x,y,step;

};

struct node s,e;

queue <node> q;

int bfs( )

{

int i,x,y;

node t,t2;

q.push(s);

bz[s.x][s.y]=1;

while (!q.empty())

{ t=q.front();

q.pop();

if (t.x==e.x && t.y==e.y) return t.step;

for (i=0; i<4; i++)

{ x=t.x+dd[i][0];

y=t.y+dd[i][1];

if (g[x][y]==0&&!bz[x][y])

{ t2.x=x; t2.y=y; t2.step=t.step+1;

bz[x][y]=1;

q.push(t2);

}

int main()

{

int n;

cin>>n;

while (n--)

{

while (!q.empty()) q.pop();

memset(bz,0,sizeof(bz));

cin>>s.x>>s.y>>e.x>>e.y;

s.step=0;

cout<<bfs( )<<endl;

}

return 0;

}

 
#include<cstdio>
#define min(x,y) x>y?y:x
int maze[9][9]={1,1,1,1,1,1,1,1,1,
    1,0,0,1,0,0,1,0,1,
    1,0,0,1,1,0,0,0,1,
    1,0,1,0,1,1,0,1,1,
    1,0,0,0,0,1,0,0,1,
    1,1,0,1,0,1,0,0,1,
    1,1,0,1,0,1,0,0,1,
    1,1,0,1,0,0,0,0,1,
    1,1,1,1,1,1,1,1,1};
int a,b,c,d,m;
void dfs(int x,int y,int s){
    if(maze[x][y]) return;
    if(x==c&&y==d){
        m=min(s,m);
        return;
    }
    s++;
    maze[x][y]=1;
    dfs(x+1,y,s);
    dfs(x,y+1,s);
    dfs(x-1,y,s);
    dfs(x,y-1,s);
    maze[x][y]=0;
}

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        m=9999;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        dfs(a,b,0);
        printf("%d
",m);
    }
    return 0;
}

View Code

#include<cstdio>
#define min(x,y) x>y?y:x
int maze[9][9]={1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,1,0,1,
1,0,0,1,1,0,0,0,1,
1,0,1,0,1,1,0,1,1,
1,0,0,0,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,0,0,0,1,
1,1,1,1,1,1,1,1,1};
int a,b,c,d,m;
void dfs(int x,int y,int s){
if(maze[x][y]) return;
if(x==c&&y==d){
m=min(s,m);
return;
}
s++;
maze[x][y]=1;
dfs(x+1,y,s);
dfs(x,y+1,s);
dfs(x-1,y,s);
dfs(x,y-1,s);
maze[x][y]=0;
}

int main(){
int n;
scanf("%d",&n);
while(n--){
  m=9999;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  dfs(a,b,0);
  printf("%d ",m);
}
return 0;
}