1029.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

#include <iostream>
using namespace std;

int room[102][502];
int fee[102][502];
int way[102][502];
int min(int a,int b){
	return a<b?a:b;
}
void print_path(int i,int j){
	if(i==1){
		cout << j <<' ';
		return ;
	}
	if(way[i][j] == 0){
		print_path(i-1,j);
		cout << j <<' ';
		return ;
	}
	if(way[i][j] == -1){
		print_path(i,j-1);
		cout << j <<' ';
		return ;
	}
	if(way[i][j] == 1){
		print_path(i,j+1);
		cout << j <<' ';
		return ;
	}
}

int main(){
	int m,n,i,j;
	cin >> m >> n;
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++)
			cin >> room[i][j];
	}
	for(j=1;j<=n;j++)
		fee[1][j] = room[1][j];
	for(i=2;i<=m;i++){
		for(j=1;j<=n;j++){
			fee[i][j] = fee[i-1][j]+room[i][j];
			way[i][j] = 0;
		}
		for(j=2;j<=n;j++){
			if(fee[i][j] > fee[i][j-1]+room[i][j]){
				fee[i][j] = fee[i][j-1]+room[i][j];
				way[i][j] = -1;
			}
		}
		for(j=n-1;j>=1;j--){
			if(fee[i][j] > fee[i][j+1]+room[i][j]){
				fee[i][j] = fee[i][j+1]+room[i][j];
				way[i][j] = 1;
			}
		}
	}
	int minnum=fee[m][1];
	for(j=1;j<=n;j++){
		minnum = min(minnum,fee[m][j]);
	}
	for(j=1;j<=n;j++){
		if(fee[m][j] == minnum){
			print_path(m,j);
			cout <<endl;
			break;
		}
	}
	system("pause");
	return 0;
}