杭州关键词排名提升/国外seo网站

★ 实验任务
众所周知，索隆是一个路痴，一天在一小岛上，他又迷路了！ ！好基友山治心急如焚，
决定出去找他，由于练成了月步，山治的速度竟然达到了正无穷！小岛上除了空地，还有盘
丝洞（简称 psd）,盘丝洞里住着可爱的妹纸，山治每次经过一个盘丝洞，都要停留一个单
位时间来欣赏妹纸， 给你一个 n*m 的地图以及山治和索隆当前位置， 山治想请你帮他算算他
最快要多久才能见到索隆。
★ 数据输入
输入第一行为两个正整数 n,m (2 <=n,m <=1000)，表示有 n 行 m 列，最左上角的坐标为
（1,1） 。
接下来 n 行，每行 m 个字符， “.”代表盘丝洞， “X”代表空地，只有‘.’和’X’两种字
符，山治通过盘丝洞需 1 个单位时间，通过空地无需花费时间。
最后两行分别表示山治和索隆的当前坐标。 （你可以假设这两个坐标都在空地上，即
‘X’ ） 。
★ 数据输出
对于每个询问，输出一行一个整数，表示山治最快见到索隆的时间。
输入示例  输出示例
6 6
..X...
XXX.X.
....X.
X.....
X.....
X.X...
3 5
6 3

3

1.广度优先搜索

策略：

1.push当前点的未访问过的上下左右点,

2.选取队列中 dis最小的那个重复步骤1

3结束条件是：从队列中选出的那个点就是终点时，返回dis

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1010;
bool G[N][N],vis[N][N];
int n,m;
struct node
{int x,y,dis;bool operator <(const node &a)const{return dis>a.dis;}
};
priority_queue<node> q;
void tovist(const node &cur,node &next)
{if(!vis[next.x][next.y]){vis[next.x][next.y]=true;next.dis=cur.dis+G[next.x][next.y];q.push(next);}
}
int bfs(const node&s,const node&e)
{node cur=s,next;cur.dis=0;int i,tmp1[]={1,-1,0,0};vis[s.x][s.y]=true;q.push(cur);while(!q.empty()){cur=q.top();q.pop();if(cur.x==e.x&&cur.y==e.y)return cur.dis;for(i=0;i<4;++i){next.x=cur.x+tmp1[i],next.y=cur.y+tmp1[3-i];if(next.x<0||next.x>=n||next.y<0||next.y>=m)continue;tovist(cur,next);}}return -1;
}
int main()
{int i,j,ans;char str[N];node s,e;while(~scanf("%d %d",&n,&m)){memset(vis,0,sizeof(vis));memset(G,0,sizeof(G));while(!q.empty())q.pop();for(i=0;i<n;++i){scanf("%s",str);for(j=0;j<m;++j)if(str[j]=='.')G[i][j]=true;}scanf("%d %d",&s.x,&s.y);--s.x,--s.y;scanf("%d %d",&e.x,&e.y);--e.x,--e.y;ans=bfs(s,e);printf("%d\n",ans);}}