题意：给出一个n*m的矩阵，1代表墙，0代表空地，不能连续k次穿过墙，求从起点到达终点的最短路的长度
给vis数组再加一维状态，表示当前还剩下的能够穿越的墙的次数，每次碰到墙，当前的k减去1,碰到0，当前的k变成最初的k
学习的这一篇
http://www.cnblogs.com/bingolibing/p/3873822.html
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 13 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 14 15 typedef long long LL; 16 const int INF = (1<<30)-1; 17 const int mod=1000000007; 18 const int maxn=105; 19 20 int g[maxn][maxn]; 21 int vis[25][25][25]; 22 int n,m,k,ans; 23 int dir[4][2]={1,0,-1,0,0,1,0,-1}; 24 25 struct node{ 26 int x,y; 27 int step; 28 int k; 29 }; 30 31 void bfs(){ 32 node u; 33 u.x=1;u.y=1;u.step=0;u.k=k; 34 queue<node> q; 35 vis[1][1][k]=1; 36 q.push(u); 37 38 while(!q.empty()){ 39 u=q.front();q.pop(); 40 if(u.x==n&&u.y==m){ 41 ans=u.step; 42 return; 43 } 44 45 node v; 46 if(u.k>=0){ 47 for(int i=0;i<4;i++){ 48 v.x=u.x+dir[i][0]; 49 v.y=u.y+dir[i][1]; 50 v.step=u.step+1; 51 52 if(g[v.x][v.y]) v.k=u.k-1; 53 else v.k=k; 54 if(v.x>=1&&v.x<=n&&v.y>=1&&v.y<=m&&!vis[v.x][v.y][v.k]){ 55 if(v.k>=0){ 56 vis[v.x][v.y][v.k]=1; 57 q.push(v); 58 } 59 60 } 61 } 62 } 63 } 64 } 65 66 int main(){ 67 int T; 68 scanf("%d",&T); 69 for(int t=1;t<=T;t++){ 70 memset(g,0,sizeof(g)); 71 memset(vis,0,sizeof(vis)); 72 cin>>n>>m>>k; 73 74 for(int i=1;i<=n;i++) 75 for(int j=1;j<=m;j++) 76 cin>>g[i][j]; 77 78 ans=-1; 79 bfs(); 80 cout<<ans<<" "; 81 } 82 return 0; 83 }
因为for循环里面的<符号写成逗号，改了好久好久---