main.cpp

全国高校BBS程序开发大赛赛题－算法项目

#include "utility"
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <assert.h>

using namespace std;


inline bool rm_comp(pair<int, int> & pair){
    if(pair.second <= 0) return true;
	else return false;
}

void mini_path(list< pair<int, vector<int> > >::iterator & it_mini, list< pair<int, vector<int> > > & path_from_accident, vector< pair<int, int> > & land_point,const int exit_index){

	cout<<"\n mini begin:\n";

	it_mini = path_from_accident.begin();	
	int last_index = (*it_mini).second.back();
	int min_length = (*it_mini).first + abs( (land_point[last_index]).first - (land_point[exit_index]).first ) + abs((land_point[last_index]).second - (land_point[exit_index]).second );;

	for(list< pair<int, vector<int> > >::iterator it_check = path_from_accident.begin(); it_check != path_from_accident.end(); ++it_check){

		cout<<"path("<<(*it_check).first<<"): ";
		for(vector<int>::iterator it_print = (*it_check).second.begin(); it_print != (*it_check).second.end(); ++it_print){
			int index = (*it_print);
			cout<<" <"<<index<<" "<<land_point[index].first<<" "<<land_point[index].second<<"> ";
		}

		if(it_mini == it_check){
			cout<<" temp_length= "<<min_length<<"\n";
			continue;
		}else{
			last_index = (*it_check).second.back();
			int temp_length = (*it_check).first + abs( (land_point[last_index]).first - (land_point[exit_index]).first ) + abs((land_point[last_index]).second - (land_point[exit_index]).second );
			cout<<" temp_length= "<<temp_length<<"\n";
			if(min_length > temp_length){
				it_mini = it_check;
				min_length = temp_length;
			}
		}		

	}   

	cout<<"mini leng: ="<<min_length<<"\n";
	cout<<"selected  path: ";
	for(vector<int>::iterator it_print = (*it_mini).second.begin(); it_print != (*it_mini).second.end(); ++it_print){
		int index = (*it_print);
		//cout<<" <"<<index<<" "<<land_point[index].first<<" "<<land_point[index].second<<"> ";
		cout<<" <"<<land_point[index].first<<" "<<land_point[index].second<<"> ";
	}
	cout<<"\n";


}


void main(){

	int DIM = 0;
	int LIFE_TIME = 0;

	cin>>DIM>>LIFE_TIME;

	int ** point_matrix = new int * [ DIM ];
	assert(NULL != point_matrix);
	for(int i=0; i<DIM; i++){
		point_matrix[i] = new int[DIM];
		assert(point_matrix[i]);
		for(int j=0; j<DIM; j++){
			cin>>point_matrix[i][j];
		}
	}
	cout<<"\n";
    
	pair<int, int> accident;
	pair<int, int> exit;
	vector< pair<int, int> > land_point;
	land_point.reserve(DIM*DIM);
	size_t accident_index = 0;
	size_t exit_index = 0;


	for(int i = 0; i<DIM; i++){
		for(int j=0; j<DIM; j++){
			if( 1 == point_matrix[i][j]){
                land_point.push_back(make_pair(i, j));
			}else if( 2 == point_matrix[i][j]){
				land_point.push_back(make_pair(i, j));
                accident.first = i;
				accident.second = j;
				accident_index = land_point.size()-1;
			}else if(3 == point_matrix[i][j]){
				land_point.push_back(make_pair(i, j));
				exit.first = i;
				exit.second = j;
				exit_index = land_point.size() -1;
			}
		}
	}

	for(vector< pair<int, int> >::iterator it_print = land_point.begin(); it_print != land_point.end(); ++it_print){
		cout<<" <"<<(*it_print).first<<" "<<(*it_print).second<<"> ";
	}
	cout<<"accident = <"<<accident.first<<" "<<accident.second<<"> \n";
	cout<<"exit = <"<<exit.first<<" "<<exit.second<<">  \n";
	


	vector< vector< pair<int, int> > >  distance_matrix;
	distance_matrix.reserve(land_point.size());

	for(size_t i =0; i<land_point.size(); i++){
		vector< pair<int, int> > distance_vector;		
		distance_vector.reserve(land_point.size());

		cout<<i<<": ";

		for(size_t j=0; j<land_point.size(); j++){
            int dis = abs( (land_point[i]).first - (land_point[j]).first ) + abs((land_point[i]).second - (land_point[j]).second );
			if(dis > LIFE_TIME) dis = 0;

			distance_vector.push_back( make_pair(j, dis) );
		}

		vector< pair<int, int> >::iterator new_end = remove_if(distance_vector.begin(), distance_vector.end(), rm_comp);
		distance_vector.erase(new_end, distance_vector.end());

		for(vector< pair<int, int> >::iterator it_print= distance_vector.begin(); it_print != distance_vector.end(); ++it_print){
            cout<<" <"<<(*it_print).first<<" "<<(*it_print).second<<"> ";
		}
		cout<<"\n";

		distance_matrix.push_back(distance_vector);
	}


	list< pair<int, vector<int> > > path_from_accident;
	bool * is_reached = new bool[land_point.size()];
	assert(NULL != is_reached);
	for(size_t i_reach = 0; i_reach<land_point.size(); ++i_reach){
		is_reached[i_reach] = false;
	}

	for(size_t i_it = 0; i_it < (distance_matrix[accident_index]).size(); i_it++){
		if(i_it == (distance_matrix[accident_index][i_it]).first) continue;

		vector<int> path;
		path.push_back(accident_index);
		path.push_back((distance_matrix[accident_index][i_it]).first);
		is_reached[(distance_matrix[accident_index][i_it]).first] = true;
        path_from_accident.push_back( make_pair( (distance_matrix[accident_index][i_it]).second, path) );
	}

    list< pair<int, vector<int> > >::iterator it_mini;
    mini_path(it_mini, path_from_accident, land_point, exit_index);

	//list< pair<int, vector<int> > >::iterator it_path;
	bool is_changed = true;
 	while (!path_from_accident.empty()) {
	  
		assert(path_from_accident.end() != it_mini);
		assert((*it_mini).second.size() >= 2);		

        int index = (*it_mini).second.back();
		if(index == exit_index) break;//succeed
		
		for(size_t j_it = 0; j_it < distance_matrix[index].size(); ++j_it ){
			int next_index = distance_matrix[index][j_it].first;
			int next_dis = distance_matrix[index][j_it].second;

			if( (next_index == index) || is_reached[next_index] ) continue;
			else{
				vector<int>::iterator it_find = find( (*it_mini).second.begin(), (*it_mini).second.end(), next_index );

				if(it_find != (*it_mini).second.end()) continue;
				else{
					vector<int> temp_path = (*it_mini).second;
	                
					temp_path.push_back(next_index);
					is_reached[next_index] = true;
					path_from_accident.push_back(make_pair( (*it_mini).first + next_dis, temp_path ) );

					is_changed = true;
				}//if

			}//if

		}//for

		path_from_accident.erase(it_mini);

		mini_path(it_mini, path_from_accident, land_point, exit_index);
		
	}//while

	if( it_mini == path_from_accident.end() ) {
		cout<<"sorry no path!\n";
		return;
	}else{
		cout<<"the mininum length is "<<(*it_mini).first<<"\n";
		for(vector<int>::iterator it_point_in_path = (*it_mini).second.begin(); it_point_in_path != (*it_mini).second.end(); ++it_point_in_path){
			int index = (*it_point_in_path);
			cout<<" --> <"<<land_point[index].first<<" , "<<land_point[index].second<<"> ";
		}
	}
	cout<<"\n";

}