#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;

	cin>>row>>column;
	
	for(i = 1; i <= row; i++){
		for(j = 1; j <= column; j++){
			cin>>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++){
				//result[char_length++] = --h;
				cout<<--h<<endl;
			}
			j=h;
			i++;
			break;
		case 'r':
			h=j;
			for(k=0;k < rooms[i][j].distance;k++){
				//result[char_length++] = ++h;
				cout<<++h<<endl;
			}
			j=h;
			i++;
			break;
		default:
			i++;
			break;
			
		}

	
	}
	
// 	for(i=char_length-1;i>=0;i--)
// 		cout<<result[i]<<endl;


	return 0;


}

• Re:菜鸟问2353题，为什么老是报OEL (44) aladdinwang 2009-03-01 19:13:47
  • Re:菜鸟问2353题，为什么老是报OEL (2114) aladdinwang 2009-03-01 19:51:26
    • Re:菜鸟问2353题，为什么老是报OEL (2316) zhengjie_ch 2009-03-01 21:22:24
      • Re:菜鸟问2353题，为什么老是报OEL (4) zhengjie_ch 2009-03-01 21:23:06