AOJ 1336 - The Last Ant
問題概要
長さlのトンネルがあり、その中のにn匹の蟻がいる。それぞれの蟻は位置piにいて向きd(dが'L'なら左、'R'なら右)を向いている。全ての蟻は1単位時間に向いている方向に1進む。そして2匹の蟻が同じ位置に到達した場合、それらの蟻の進行方向が反転する。全ての蟻がトンネルから出るまでにかかる時間と最後にトンネル内にいる蟻(複数いる場合は一番左の蟻)の番号を出力せよ。
制約
- 1 ≤ n ≤ 20
- n+1 ≤ l ≤ 100
解法
時間を1ずつ進めていき蟻の動きをシミュレーションする。
コード
#include <bits/stdc++.h> using namespace std; #define MAX 110 bool check(int ant[MAX],int L){ for(int i = 0 ; i < L ; i++){ if(ant[i] != 0) return false; } return true; } int main(){ int N,L,p; char d; while(cin >> N >> L, N){ int ant[MAX]={0}; vector<int> tunnel[MAX],id[MAX]; L--; for(int i = 0 ; i < N ; i++){ cin >> d >> p; ant[p-1]++; id[p-1].push_back(i+1); tunnel[p-1].push_back((d == 'L' ? 1 : 2)); } int t = 0,last; while(!check(ant,L)){ vector<int> next[MAX],nid[MAX]; last = -1; for(int i = 0 ; i < L ; i++){ next[i].clear(); nid[i].clear(); if(ant[i] && last == -1){ last = id[i][0]; } } for(int i = 0 ; i < L ; i++){ while(tunnel[i].size()){ if(tunnel[i][0] == 1){ tunnel[i].erase(tunnel[i].begin()); if(i-1 >= 0){ next[i-1].push_back(1); nid[i-1].push_back(id[i][0]); id[i].erase(id[i].begin()); } }else if(tunnel[i][0] == 2){ tunnel[i].erase(tunnel[i].begin()); if(i+1 < L){ next[i+1].push_back(2); nid[i+1].push_back(id[i][0]); id[i].erase(id[i].begin()); } } } } for(int i = 0 ; i < L ; i++){ tunnel[i] = next[i]; id[i] = nid[i]; if(tunnel[i].size() == 2){ swap(tunnel[i][0],tunnel[i][1]); } ant[i] = tunnel[i].size(); } t++; } cout << t << " " << last << endl; } return 0; }