讨论 / 谁给几组数据。。。
1516050107 2016-08-03 16:29:26
点我顶贴 收藏 删除
#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];

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<0||y<0||x>=n||y>=n||vis[x][y]||ma[x][y]=='1')

return 1;

return 0;

}

int BFS()

{

priority_queue <state> Q;

state st,next;

st.x=a-1;

st.y=b-1;

st.step=0;

Q.push(st);

vis[a][b]=1;

while(!Q.empty())

{

st=Q.top();

Q.pop();

if(st.x==X-1&&st.y==Y-1)

return st.step;

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;

if(next.x==X-1&&next.y==Y-1)

return st.step+1;

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

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

next.step=st.step+1;

Q.push(next);

}

}

}

return 0;

}

int main()

{

cin>>n;

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

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

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

cin>>ma[i][j];

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

cout<<BFS()<<endl;

return 0;

}

查看更多回复
提交回复