codeforces 540 C Ice Cave【BFS】

题意：给出一个n*m的矩阵，“.”代表完整的冰，“X”代表破碎的冰，现在为了前进，需要掉下去一层，唯一的方法就是从破碎的冰上面掉下去

然后给出起点还有终点，问能否可达

即为到达终点的时候，终点必须是破碎的冰，这样才能够保证只掉了一层

然后这个也说明了节点该怎么扩展，如果当前跳到的点是"X"（破碎的冰）,且当前点不是终点，那么这个点就不用加入队列了（因为它还没有到达终点就落下去了）

如果当前点是“.”完整的冰，那么跳上去之后，这一点变成破碎的冰"X",再把这一点加入队列，

就这么扩展搜下去

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 char g[][];

 int n,m,flag;

 int st1,st2,en1,en2;

 int dir[][]={,,-,,,,,-};

 struct node{

     int x,y;

 };

 void bfs(){

     node u;

     u.x=st1;u.y=st2;

     queue<node> q;

     q.push(u);

     node v;

     while(!q.empty()){

         u=q.front();q.pop();

         for(int i=;i<;i++){

             v.x=u.x+dir[i][];

             v.y=u.y+dir[i][];

             if(v.x==en1&&v.y==en2&&g[v.x][v.y]=='X'){

                 flag=;

                 return;

             }

             if(v.x<||v.x>n||v.y<||v.y>m) continue;

             if(g[v.x][v.y]=='X') continue;

             q.push(v);

             g[v.x][v.y]='X';

         }

     }

 }

 int main(){

     scanf("%d %d",&n,&m);

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

      for(int j=;j<=m;j++)

       cin>>g[i][j];

       cin>>st1>>st2;

       cin>>en1>>en2;

       flag=;

       bfs();

       if(flag) printf("YES\n");

       else printf("NO\n");

      return ;

 }

当时做的时候，没有理清楚节点应该怎么扩展，因为根本没有注意只需要落一层，而且因为要到达终点，那下落的一层一定是在终点

哎-----------加油啊 gooooooooooooooooooooooo--------