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();
}