POJ_4115(壁貫通回数のあるBFSアルゴリズム)
15601 ワード
POJ_4115,壁を通る回数(エネルギー)のBFSのテーマがあって、コードは参考になります
#include
#include
using namespace std;
struct point{
// , , ,
int r,c,alltime,chance;
bool cango;
}points[200][200];
queue <point> q;
int row,col,endr,endc;
int bfs(){
while(!q.empty()){
point curr=q.front();
q.pop();
if(curr.r==endr && curr.c==endc) return curr.alltime;
int choose[4][2]={{curr.r-1,curr.c},{curr.r+1,curr.c},{curr.r,curr.c-1},{curr.r,curr.c+1}};
for(int i=0;i<4;i++){
int nextr=choose[i][0],nextc=choose[i][1];
// BFS, ,
// , , ( )
// , ( , )
if(nextr>=0 && nextc>=0 && nextr<row && nextc<col && curr.chance>points[nextr][nextc].chance){
points[nextr][nextc].alltime=curr.alltime+1;
points[nextr][nextc].chance=curr.chance;
if(points[nextr][nextc].cango) q.push(points[nextr][nextc]);
else if(curr.chance>0){
points[nextr][nextc].chance--;
q.push(points[nextr][nextc]);
}
}
}
}
return -1;
}
int main(){
int chance; cin>>row>>col>>chance;
for(int i=0;i<row;i++)
for(int j=0;j<col;j++){
points[i][j].r=i;
points[i][j].c=j;
points[i][j].alltime=0;
// -1( BFS )
points[i][j].chance=-1;
char c; cin>>c;
if(c=='#') points[i][j].cango=0;
else{
points[i][j].cango=1;
if(c=='@'){
points[i][j].chance=chance;
q.push(points[i][j]);
}
else if(c=='+'){
endr=i;
endc=j;
}
}
}
cout<<bfs();
}