SRM 405 250pt: RelativePath

問題概要

AとBの絶対パスが与えられるのでAから見たBの相対パスを返す問題。

考えたこと

• 一瞬LCAかと思ったがそこまで面倒な話ではない。
• 先頭から順に一致する部分を削って、いくつ戻るかカウントして../を付け加え、その後行き先の末尾をくっつけてやればよい。
• 楽な実装方法考えてるうちに時間が削られたけど実装時間自体は割と短く済ませられた。AC。

practiceで通ったコード

#include <sstream>
#include <string>
#include <vector>
#include <iostream>
using namespace std;

struct RelativePath {

	string makeRelative(string path, string currentDir) {
		for(int i=0; i<(int)path.length(); i++)if(path[i] == '/'){
			path[i] = ' ';
		}
		for(int i=0; i<(int)currentDir.length(); i++)if(currentDir[i] == '/'){
			currentDir[i] = ' ';
		}
		stringstream a(path), b(currentDir);
		vector<string> as, bs;
		string str;
		while(a>>str) as.push_back(str);
		while(b>>str) bs.push_back(str);

		string ret = "";
		int eq = 0;
		for(; eq<(int)as.size() && eq<(int)bs.size() && as[eq] == bs[eq]; eq++);
		for(int i=0; i<(int)bs.size() - eq; i++){
			ret += "../";
		}
		for(int i=eq; i<(int)as.size(); i++){
			ret += as[i] + "/";
		}

		return ret.substr(0, (int)ret.length() - 1);
	}

};