問題
http://topcoder.bgcoder.com/print.php?id=416
ある島にある宝を探しにいきたい。
島のマップが与えられ、陸地の場所と宝の場所がしめされている。
宝の場所はあいまいであり必ずしも正確ではないが、
スタート地点からどのように移動すれば宝の位置にたどり着けるかがわかっている。
スタート地点は海から島にたどり着くため、海に隣接していないといけない。
このとき、宝の場所がどこにあるかを求める。
宝の場所が複数存在する場合は、地図の宝の位置とのユークリッド距離が最も近いものになる。ユークリッド距離も同じ場合はもっとも北にあるもの、北の位置も一緒であればもっとも西にあるものになる。
解き方
問題文が長く、スタート位置が海に隣接していなければいけないことを読み落としてしまった。これがわかれば単純に実装するだけ。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
vector<string> island;
int w,h;
class TreasureHunt {
public:
bool inside(int x,int y){
return (0<=x&&x<h && 0<=y&&y<w && island[x][y]!='.');
}
vector<int> findTreasure(vector<string> island_, vector<string> instructions) {
island=island_;
w=island[0].size(),h=island.size();
int tx,ty;
FORE(i,0,h)FORE(j,0,w)if(island[i][j]=='X')tx=i,ty=j;
vector<pair<int,int> > p;
char dir[]={'W','E','N','S'};
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
FORE(i,0,instructions.size()){
stringstream out(instructions[i]);
char ch;
int num;
out>>ch>>num;
FORE(j,0,4){
if(dir[j]==ch)FORE(k,0,num)p.push_back(make_pair(dx[j],dy[j]));
}
}
vector<pair<int,pair<int,int> > > tmp;
FORE(i,0,h){
FORE(j,0,w){
if(!inside(i,j))continue;
int x=i,y=j;
int ok=0;
FORE(k,0,4)if(!inside(x+dx[k],y+dy[k]))ok=1;
if(!ok)goto fail;
FORE(k,0,p.size()){
x+=p[k].first,y+=p[k].second;
if(!inside(x,y))goto fail;
}
int cost=(tx-x)*(tx-x)+(ty-y)*(ty-y);
tmp.push_back(make_pair(cost,make_pair(x,y)));
fail:;
}
}
vector<int> ans;
sort(all(tmp));
if(tmp.empty())return ans;
ans.push_back(tmp[0].second.second);
ans.push_back(tmp[0].second.first);
return ans;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
vector<string> island;
int w,h;
class TreasureHunt {
public:
bool inside(int x,int y){
return (0<=x&&x<h && 0<=y&&y<w && island[x][y]!='.');
}
vector<int> findTreasure(vector<string> island_, vector<string> instructions) {
island=island_;
w=island[0].size(),h=island.size();
int tx,ty;
FORE(i,0,h)FORE(j,0,w)if(island[i][j]=='X')tx=i,ty=j;
vector<pair<int,int> > p;
char dir[]={'W','E','N','S'};
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
FORE(i,0,instructions.size()){
stringstream out(instructions[i]);
char ch;
int num;
out>>ch>>num;
FORE(j,0,4){
if(dir[j]==ch)FORE(k,0,num)p.push_back(make_pair(dx[j],dy[j]));
}
}
vector<pair<int,pair<int,int> > > tmp;
FORE(i,0,h){
FORE(j,0,w){
if(!inside(i,j))continue;
int x=i,y=j;
int ok=0;
FORE(k,0,4)if(!inside(x+dx[k],y+dy[k]))ok=1;
if(!ok)goto fail;
FORE(k,0,p.size()){
x+=p[k].first,y+=p[k].second;
if(!inside(x,y))goto fail;
}
int cost=(tx-x)*(tx-x)+(ty-y)*(ty-y);
tmp.push_back(make_pair(cost,make_pair(x,y)));
fail:;
}
}
vector<int> ans;
sort(all(tmp));
if(tmp.empty())return ans;
ans.push_back(tmp[0].second.second);
ans.push_back(tmp[0].second.first);
return ans;
}
};