> 
> 加过注释了
> 
> #include <iostream>
> #include <fstream>
> #include <cstring>
> using namespace std;
> 
> 
> 
> 
> typedef struct s_room{
> 	int cost;//到达该房间的最低成本(包括贿赂本房间秘书的成本)
> 	int distance;//路线为左或右时，记录距离
> 	char dir;//最低成本的路线方向
> }t_room;
> 
> 
> 
> int main(int argc, char* args[]){
> 	int column;
> 	int row;
> 	int input[101][501];
> 	int i,j;
> 	t_room rooms[101][501];
> 	ifstream in("input.txt");
> 	t_room default_room;
> 
> 	default_room.dir = 'd';
> 	default_room.distance = 1;
> 
> 	in>>row>>column;
> 	
> 	for(i = 1; i <= row; i++){
> 		for(j = 1; j <= column; j++){
> 			in>>input[i][j];
> 		}
> 	}
> 	//初始化底楼
> 	for(j=1;j<=column;j++)
> 		rooms[row][j].cost = input[row][j];
> 	
> 	for(i=row-1; i >= 1; i--){
> 		for(j = 1; j <= column; j++){
> 			int j2 = j, cost, row_cost;
> 			
> 			memcpy(&rooms[i][j], &default_room, sizeof(t_room));		
> 			
> 			cost = rooms[i+1][j].cost;
> 			row_cost = 0;
> 			while(--j2>=1){
> 				row_cost += input[i][j2];
> 				
> 				if(cost > rooms[i+1][j2].cost + row_cost){
> 					cost = rooms[i+1][j2].cost+row_cost;
> 					rooms[i][j].dir = 'l';
> 					rooms[i][j].distance = j-j2;
> 				}
> 				
> 			}
> 			
> 			j2=j;
> 			row_cost = 0;
> 			while(++j2<=column){
> 				row_cost += input[i][j2];
> 				if(cost > rooms[i+1][j2].cost + row_cost){
> 					cost = rooms[i+1][j2].cost+row_cost;
> 					rooms[i][j].dir = 'r';
> 					rooms[i][j].distance = j2-j;
> 				}
> 			}
> 			rooms[i][j].cost = cost + input[i][j];
> 		}
> 
> 	}
> 	//在顶楼找出总成本最低的房间
> 	int min_num = 1, min_cost = rooms[1][1].cost;
> 	for(j = 2; j <= column; j++){
> 		if(min_cost > rooms[1][j].cost){
> 			min_cost = rooms[1][j].cost;
> 			min_num = j;
> 		}
> 	}
> 
> 	i=1;
> 	j=min_num;	
> 	int k,h;
> 	while(i<=row){		
> 		cout<<j<<endl;
> 		switch(rooms[i][j].dir){
> 		case 'd':
> 			i++;	
> 			break;
> 		case 'l':
> 			h=j;
> 			for(k=0; k < rooms[i][j].distance; k++){			
> 				cout<<--h<<endl;
> 			}
> 			j=h;
> 			i++;
> 			break;
> 		case 'r':
> 			h=j;
> 			for(k=0;k < rooms[i][j].distance;k++){				
> 				cout<<++h<<endl;
> 			}
> 			j=h;
> 			i++;
> 			break;
> 		default:
> 			i++;
> 			break;
> 			
> 		}
> 
> 	
> 	}
> 	
> 
> 
> 
> 	return 0;
> 
> 
> }

• Re:菜鸟问2353题，为什么老是报OEL (4) zhengjie_ch 2009-03-01 21:23:06