travsrccvar.cpp

汽车加油行驶问题 这个问题限制条件很多！我想了两天才想出一个动态规划程序！已经经过测试

/*
  汽车加油问题
  2005-1-1 18:14 Release v1.0
  2005-1-1 19:58 Release v1.0.1  修正输入时变转置
*/
# include <fstream.h>

//# define MCOST 0xffffffff  
typedef unsigned long ulong;


void writeData(ulong cost);
ulong minpCost(int x, int y);
ulong minppCost(int x1, int y1, int x2, int y2);
void p2p(int x1, int y1, int x2, int y2);
void pp2p(int x1, int y1, int x2, int y2, int x3, int y3);
void renewUp(int x, int y);
void renewDown(int x, int y);
void renewLeft(int x, int y);
void renewRight(int x, int y);


int N, K, A, B, C;
int level = 2;  //起始层为起点
ulong MCOST = 0xffffffff; 
ulong cost[102][102][12];
int pos[102][102];  //存放加油站位置信息


int main(){

	ifstream infile("input.txt");
	if (!infile){
		cout << "无法打开input.txt\n";
		return -1;
	}
	infile >> N >> K >> A >> B >> C;

	//异常处理
	if ( (N < 2) || (N > 100) || (K < 2) || (K > 10) || (A < 0) || (B < 0) || (C < 0) ){
		cout << "输入数据有误\n";
		return -1;
	}

	//正常处理
	int ia, ib, ic;
	for (ia = 1; ia <= N; ia++){
		for (ib = 1; ib <= N; ib++){
			infile >> pos[ib][ia];
		}
	}
	infile.close();

	for (ia = 1; ia <= N; ia++){
		for (ib = 1; ib <= N; ib++){
			for (ic = 1; ic <= K; ic++)
				cost[ia][ib][ic] = MCOST;
		}
	}

	cost[1][1][K] = 0;  //起点费用为0

	for (level = 3; level <= N + 1; level++){  //处理上三角范围,含对角线level=N+1
		p2p(level - 2, 1, level - 1, 1);  //向y轴正向推进
		p2p(1, level - 2, 1, level - 1);  //向x轴正向推进
		for (int id = level - 2; id >= 2; id--){
			pp2p(id - 1, level - id, id, level - id - 1, id, level - id);  //(id, level-id)点的左点和上点来更新
			//从(id, level-id)开始倒退更新其余的点
			renewUp(id, level - id - 1);
			renewLeft(id - 1, level - id);
		}
	}

	for (level = N + 2; level <= 2 * N - 1; level++){ //处理下三角范围,不含对角线
		for (int id = level - N; id <= N; id++){
			pp2p(id - 1, level - id, id, level - id - 1, id, level - id);  //(id, level-id)点的左点和上点来更新
			//从(id, level-id)开始倒退更新其余的点
			renewUp(id, level - id - 1);
			renewLeft(id - 1, level - id);

		}
	}

	ulong mincost = minppCost(N, N - 1, N - 1, N);  //最后两个点的最小费用就是到终点的最小费用
	writeData(mincost);

	return 0;
}



void writeData(ulong cost){
	ofstream outf("output.txt");
	if (!outf)
		cout << "无法打开文件output.txt\n";
	else{
		cout << "最小费用是" << cost << endl;
		outf << cost;
	}
	outf.close();
}


ulong minpCost(int x, int y){
	ulong mincost = MCOST;
	for (int ir = 1; ir <= K; ir++)
		if (cost[x][y][ir] < mincost)
			mincost = cost[x][y][ir];
	//如果mincost = MCOST则可能有异常
	return mincost;
}

ulong minppCost(int x1, int y1, int x2, int y2){
	ulong mc1 = minpCost(x1, y1);
	ulong mc2 = minpCost(x2, y2);
	return ( (mc1 < mc2) ? mc1 : mc2);
}

void p2p(int x1, int y1, int x2, int y2){
	if (pos[x2][y2] == 0){ //不是加油站
		for (int ir = 2; ir <= K; ir++){
			if (cost[x1][y1][ir] == MCOST)  //没有改进
				continue;
			else
				cost[x2][y2][ir - 1] = cost[x1][y1][ir];
		}
		if (cost[x1][y1][1] != MCOST)
			//设油库并加油
			cost[x2][y2][K] = cost[x1][y1][1] + C + A;
	}
	else //(x2, y2)为加油站
		cost[x2][y2][K] = minpCost(x1, y1) + A;
}

void pp2p(int x1, int y1, int x2, int y2, int x3, int y3){
	if (pos[x3][y3] == 0){ //非加油站
		for (int ir = 2; ir <= K; ir++)
			if ((cost[x1][y1][ir] == MCOST) && (cost[x2][y2][ir] == MCOST))
				continue;
			else
				cost[x3][y3][ir - 1] = (cost[x1][y1][ir] < cost[x2][y2][ir]) ? cost[x1][y1][ir] : cost[x2][y2][ir];
		cost[x3][y3][K] = (cost[x1][y1][1] < cost[x2][y2][1]) ? cost[x1][y1][1] : cost[x2][y2][1];
		if (cost[x3][y3][K] != MCOST)
			cost[x3][y3][K] += C + A;
	}
	else{ //是加油站
		cost[x3][y3][K] = minppCost(x1, y1, x2, y2) + A;
	}
}

void renewUp(int x, int y){ //从下向上, (x,y)为被更新的点
	if (y == 0) return;  //防止出界
	bool isUpdate = false;
	if (pos[x][y] == 0){ //非加油站
		for (int ir = 2; ir <= K; ir++)
			if (cost[x][y + 1][ir] == MCOST)
				continue;
			else
				if (cost[x][y][ir - 1] > cost[x][y + 1][ir] + B){
					cost[x][y][ir - 1] = cost[x][y + 1][ir] + B;
					isUpdate = true;
				}
		if ( (cost[x][y + 1][1] != MCOST) && 
			(cost[x][y][K] > cost[x][y + 1][1] + A + B + C ) ){
			 cost[x][y][K] = cost[x][y + 1][1] + A + B + C;
			 isUpdate = true;
		}
	}
	else{  //是加油站
		ulong tmp = minpCost(x, y + 1) + A + B;
		if (cost[x][y][K] > tmp){
			cost[x][y][K] = tmp;
			isUpdate = true;
		}
	}
	if ( !isUpdate ) return; //无任何更新则返回
	renewUp(x, y - 1);
	renewLeft(x - 1, y);
	renewRight(x + 1, y);
}

void renewDown(int x, int y){ //从上向下, (x,y)为被更新的点
	if (x + y > level) return;  //在已搜索过的上三角范围内更新
	bool isUpdate = false;
	if (pos[x][y] == 0){ //非加油站
		for (int ir = 2; ir <= K; ir++)
			if (cost[x][y - 1][ir] == MCOST)
				continue;
			else
				if (cost[x][y][ir - 1] > cost[x][y - 1][ir]){
					cost[x][y][ir - 1] = cost[x][y - 1][ir];
					isUpdate = true;
				}
		if ( (cost[x][y - 1][1] != MCOST) && 
			(cost[x][y][K] > cost[x][y - 1][1] + A + C ) ){
			 cost[x][y][K] = cost[x][y - 1][1] + A + C;
			 isUpdate = true;
		}
	}
	else{  //是加油站
		ulong tmp = minpCost(x, y - 1) + A;
		if (cost[x][y][K] > tmp){
			cost[x][y][K] = tmp;
			isUpdate = true;
		}
	}
	if ( !isUpdate ) return; //无任何更新则返回
	renewDown(x, y + 1);
	renewLeft(x - 1, y);
	renewRight(x + 1, y);
}

void renewLeft(int x, int y){ //从右向左, (x,y)为被更新的点
	if (x == 0) return;  //防止出界
	bool isUpdate = false;
	if (pos[x][y] == 0){ //非加油站
		for (int ir = 2; ir <= K; ir++)
			if (cost[x + 1][y][ir] == MCOST)
				continue;
			else
				if (cost[x][y][ir - 1] > cost[x + 1][y][ir] + B){
					cost[x][y][ir - 1] = cost[x + 1][y][ir] + B;
					isUpdate = true;
				}
		if ( (cost[x + 1][y][1] != MCOST) && 
			(cost[x][y][K] > cost[x + 1][y][1] + A + B + C ) ){
			 cost[x][y][K] = cost[x + 1][y][1] + A + B + C;
			 isUpdate = true;
		}
	}
	else{  //是加油站
		ulong tmp = minpCost(x + 1, y) + A + B;
		if (cost[x][y][K] > tmp){
			cost[x][y][K] = tmp;
			isUpdate = true;
		}
	}
	if ( !isUpdate ) return; //无任何更新则返回
	renewUp(x, y - 1);
	renewDown(x, y + 1);
	renewLeft(x - 1, y);
}

void renewRight(int x, int y){ //从左向右, (x,y)为被更新的点
	if (x + y > level) return; //在已搜索过的上三角范围内更新
	bool isUpdate = false;
	if (pos[x][y] == 0){ //非加油站
		for (int ir = 2; ir <= K; ir++)
			if (cost[x - 1][y][ir] == MCOST)
				continue;
			else
				if (cost[x][y][ir - 1] > cost[x - 1][y][ir]){
					cost[x][y][ir - 1] = cost[x - 1][y][ir];
					isUpdate = true;
				}
		if ( (cost[x - 1][y][1] != MCOST) && 
			(cost[x][y][K] > cost[x - 1][y][1] + A + C ) ){
			 cost[x][y][K] = cost[x - 1][y][1] + A + C;
			 isUpdate = true;
		}
	}
	else{  //是加油站
		ulong tmp = minpCost(x - 1, y) + A;
		if (cost[x][y][K] > tmp){
			cost[x][y][K] = tmp;
			isUpdate = true;
		}
	}
	if ( !isUpdate ) return; //无任何更新则返回
	renewUp(x, y - 1);
	renewDown(x, y + 1);
	renewRight(x + 1, y);
}