SRM541 DIV2 -Level2

問題


①複数の座標が与えられる。
 それぞれの座標にたいして、NWSEの方向が与えられる。
②それぞれの座標には蟻がいて指定された方向に進む。
③蟻は他の蟻とぶつかったときにフィールドから消える。
 フィールドの大きさに制限はない。
④このとき、最後に残る蟻の数を返す。

解き方


単純にシミュレーションすることで解くことができる。

Challenge
このとき、1マスずつシミュレーションすると、
蟻の距離の差が1マスで方向が互い違いの時すれちがってしまいシステムエラーとなる。

1マスごとの処理で良いか、「選んだ単位の処理でミスがないか」チェックが必要。

コード


class AntsMeet {

public: int countAnts(vector<int> x, vector<int> y, string direction) {
int n=x.size(),ans=0;
vector<int> check(n,0);
double cx[n],cy[n];

FORE(i,0,n){
cx[i]=x[i];
cy[i]=y[i];
}

FORE(i,0,5000){
FORE(j,0,n){
if(check[j]==1)continue;
if(direction[j]=='N')cy[j]+=0.5;
if(direction[j]=='W')cx[j]-=0.5;
if(direction[j]=='E')cx[j]+=0.5;
if(direction[j]=='S')cy[j]-=0.5;
}

FORE(j,0,n){
int used=0;
if(check[j]==1)continue;
FORE(k,j+1,n){
if(check[k]==1)continue;
if(cx[j]==cx[k] && cy[j]==cy[k]){
check[k]=1;
used=1;
}
}
if(used==1)check[j]=1;
}
}
FORE(i,0,n)if(check[i]==0)ans++;
return ans;
}

};
このエントリーをはてなブックマークに追加