UVa116

題敘

http://domen111.github.io/UVa-Easy-Viewer/?116

想法

實作dfs很簡單，但是需要能回朔解
這邊想到用陣列去記錄每個點要前往的x座標，而y座標固定是+1，故不紀錄
在更新Min_dis要特別注意維護x較小的要在前
並且當Min_dis已經為最小值時DFS可以直接return減少遞迴時間

Code

//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int m,n,arr[15][105],Min_dis[15][105],to[15][105];
int dir[3]={-1,0,1};

int next(int x){
	if(x<0)
		return m-1;
	else if(x>=m)
		return 0;
	else
		return x;
}

int dfs(int x,int y){
	if(y+1==n){
		return Min_dis[x][y]=arr[x][y];
	}
	if(Min_dis[x][y]!=2147483647)
		return Min_dis[x][y];
	for(int i=0 ; i<3 ; i++){
		int nx=next(x+dir[i]);
		int ny=y+1;
		int dis=dfs(nx,ny);
		if(dis+arr[x][y]<Min_dis[x][y]){
			Min_dis[x][y]=dis+arr[x][y];
			to[x][y]=nx;
		}
		else if(dis+arr[x][y]==Min_dis[x][y] && to[x][y]>nx){
			to[x][y]=nx;
		}
	}
	return Min_dis[x][y];
}

int main(){
	IOS
	while(cin>>m>>n){
		//input
		for(int i=0 ; i<m ; i++){
			for(int j=0 ; j<n ; j++){
				Min_dis[i][j]=2147483647;
				cin>>arr[i][j];
			}
		}
		int ans=0,tot=2147483647;
		for(int i=0 ; i<m ; i++){
			int res=dfs(i,0);
			if(res<tot){
				tot=res;
				ans=i;
			}
		}
		bool out=false;
		for(int start=ans,j=0 ; j<n ; j++){
			if(out)
				cout<<" ";
			else
				out=true;
			cout<<start+1;
			start=to[start][j];
		}
		cout<<'\n';
		cout<<tot<<"\n";
	}
	return 0;
}

複雜度分析

每次狀態轉移複雜度為 $O(1)$，總共有$n\times m$ 種狀態
總複雜度 $O(nm)$