讨论 / 超时?
1516050107 2016-08-03 02:11:04
点我顶贴 收藏 删除
#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<cstdlib>

#include<sstream>

#include<set>

#include<algorithm>

#include<queue>

#include<stack>

#include<vector>

#include<ctime>

#include<fstream>

#include<iomanip>

using namespace std;

#define M 1005

int n,m,a,b,X,Y;

int vis[M][M],flag=0;

char ma[M][M];

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

int num=1;

struct state

{

int x,y,step;

friend bool operator<(state x1,state x2){

return x1.step>x2.step; //优先队列,按照步数从小到大排列(最小优先队列)

}

};

bool check(int x,int y)

{

if(x<1||y<1||x>n||y>n||vis[x][y]||ma[x][y]=='1')

return 1;

return 0;

}

void BFS()

{

if(flag)

return ;

priority_queue <state> Q;

state st,next;

st.x=a;

st.y=b;

st.step=0;

Q.push(st);

vis[a][b]=1;

while(!Q.empty())

{

st=Q.top();

Q.pop();

if(st.x==X&&st.y==Y){

flag=1;

cout<<st.step<<endl;

return ;

}

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

{

next.x=st.x+dir[i][0];

next.y=st.y+dir[i][1];

if(check(next.x,next.y))

continue;

if(!vis[next.x][next.y])

{

//cout<<"Case:"<<num++<<" "<<next.x<<" "<<next.y<<endl;

vis[next.x][next.y]=1;

if(ma[next.x][next.y]=='0')

next.step=st.step+1;

Q.push(next);

}

}

}

return ;

}

int main()

{

cin>>n;

memset(vis,0,sizeof(vis));

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

cin>>ma[i][j];

cin>>a>>b>>X>>Y;

BFS();

return 0;

}

#1 1516050107@2016-08-03 02:35:07
回复 删除
。。。不用优先队列就过了
查看更多回复
提交回复