uva1600 (bfs迷宫)

#include<cstdio>
#include<string>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=30;
const int block=1;
int maze[maxn][maxn];
int r,c,k;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
struct node{int x;int y;int step;int kk;
};
node s,e,n,fa;inline bool legal (int x,int y)
{return x>0&&y>0&&x<=r&&y<=c;
}int bfs()
{queue<node> q;q.push(s);maze[s.x][s.y]=block;while(!q.empty()){fa=q.front();q.pop();for(int j=0;j<4;j++){n.x=dx[j]+fa.x;n.y=dy[j]+fa.y;if(!legal(n.x,n.y)){continue;}if(maze[n.x][n.y]==1&&fa.kk>0){n.step=fa.step+1;n.kk=fa.kk-1;q.push(n);maze[n.x][n.y]=block;}if(maze[n.x][n.y]==0){n.step=fa.step+1;n.kk=k;q.push(n);maze[n.x][n.y]=block;}//maze[n.x][n.y]=block;//n.step=fa.step+i+1;if(n.x==r&&n.y==c)return n.step;//q.push(n);}}return -1;
}int main()
{int T;scanf("%d",&T);while(T--){memset(maze,0,sizeof(maze));scanf("%d%d",&r,&c);s.x=1;s.y=1;e.x=r;e.y=c;scanf("%d",&k);s.kk=k;for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)scanf("%d",&maze[i][j]);printf("%d\n",bfs());}
}

#include<cstdio>
#include<string>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=30;
const int block=1;
int maze[maxn][maxn];
int r,c,k;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
struct node{int x;int y;int step;
};
node s,e,n,fa;inline bool legal (int x,int y)
{return x>0&&y>0&&x<=r&&y<=c&&!maze[x][y];
}int bfs()
{queue<node> q;q.push(s);maze[s.x][s.y]=block;while(!q.empty()){fa=q.front();q.pop();for(int i=0;i<=k;i++)for(int j=0;j<4;j++){n.x=(i+1)*dx[j]+fa.x;n.y=(i+1)*dy[j]+fa.y;if(!legal(n.x,n.y)){continue;}maze[n.x][n.y]=block;n.step=fa.step+i+1;if(n.x==r&&n.y==c)return n.step;q.push(n);}}return -1;
}int main()
{int T;scanf("%d",&T);while(T--){memset(maze,0,sizeof(maze));scanf("%d%d",&r,&c);s.x=1;s.y=1;e.x=r;e.y=c;scanf("%d",&k);for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)scanf("%d",&maze[i][j]);if(r==1&&c==1)printf("0\n");elseprintf("%d\n",bfs());}
}