题意：给出一个n*m的矩阵，“.”代表完整的冰，“X”代表破碎的冰，现在为了前进，需要掉下去一层，唯一的方法就是从破碎的冰上面掉下去
然后给出起点还有终点，问能否可达
即为到达终点的时候，终点必须是破碎的冰，这样才能够保证只掉了一层
然后这个也说明了节点该怎么扩展，如果当前跳到的点是"X"（破碎的冰）,且当前点不是终点，那么这个点就不用加入队列了（因为它还没有到达终点就落下去了）
如果当前点是“.”完整的冰，那么跳上去之后，这一点变成破碎的冰"X",再把这一点加入队列，
就这么扩展搜下去
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 13 14 typedef long long LL; 15 const int INF = (1<<30)-1; 16 const int mod=1000000007; 17 const int maxn=100005; 18 19 char g[505][505]; 20 int n,m,flag; 21 int st1,st2,en1,en2; 22 int dir[4][2]={1,0,-1,0,0,1,0,-1}; 23 24 struct node{ 25 int x,y; 26 }; 27 28 29 void bfs(){ 30 node u; 31 u.x=st1;u.y=st2; 32 queue<node> q; 33 q.push(u); 34 35 node v; 36 while(!q.empty()){ 37 u=q.front();q.pop(); 38 39 for(int i=0;i<4;i++){ 40 v.x=u.x+dir[i][0]; 41 v.y=u.y+dir[i][1]; 42 43 if(v.x==en1&&v.y==en2&&g[v.x][v.y]=='X'){ 44 flag=1; 45 return; 46 } 47 if(v.x<1||v.x>n||v.y<1||v.y>m) continue; 48 if(g[v.x][v.y]=='X') continue; 49 50 q.push(v); 51 g[v.x][v.y]='X'; 52 } 53 } 54 } 55 56 57 int main(){ 58 scanf("%d %d",&n,&m); 59 for(int i=1;i<=n;i++) 60 for(int j=1;j<=m;j++) 61 cin>>g[i][j]; 62 63 cin>>st1>>st2; 64 cin>>en1>>en2; 65 66 flag=0; 67 bfs(); 68 69 if(flag) printf("YES "); 70 else printf("NO "); 71 72 return 0; 73 }
当时做的时候，没有理清楚节点应该怎么扩展，因为根本没有注意只需要落一层，而且因为要到达终点，那下落的一层一定是在终点
哎-----------加油啊 gooooooooooooooooooooooo--------