AOJ 0210 - The Squares

問題 : ザ・スクエアーズ

解法 :

シミュレーションをする. しかしバグりやすい...
もっと速く実装して確実に点を取って行きたい.

コード :

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

char s[] = "ENWS";
int rev[128];
int dy[] = {0, -1, 0, 1};
int dx[] = {1, 0, -1, 0};

struct Person {
	int y, x;
	char dir;
	int candy, candx;
	Person(int y, int x, char dir) : y(y), x(x), dir(dir){}
	Person(){}
};

char map[32][32];

void moveIt(vector<Person> &v, int num, int i, int j)
{
	if (map[i][j] == 'X'){
		map[v[num].y][v[num].x] = '.';
		v.erase(v.begin() + num, v.begin() + num + 1);
	}
	else {
		map[v[num].y][v[num].x] = '.';
		v[num].y = v[num].candy; v[num].x = v[num].candx;
		map[v[num].y][v[num].x] = v[num].dir;
	}
}

int main()
{
	int w, h;
	
	for (int i = 0; i < 4; i++) rev[s[i]] = i;
	while (scanf("%d %d", &w, &h) && w){
		vector<Person> v;
		
		for (int i = 0; i < h; i++){
			scanf("%s", map[i]);
			for (int j = 0; j < w; j++){
				if (map[i][j] != 'X' && map[i][j] != '#' && map[i][j] != '.'){
					v.push_back(Person(i, j, map[i][j]));
				}
			}
		}
		
		int time = 0;
		int count[32][32];
		while (time <= 180){
			if (v.size() == 0){
				printf("%d\n", time);
				goto next;
			}
			
			for (int i = 0; i < h; i++)
				for (int j = 0; j < w; j++)
					count[i][j] = 0;
			
			for (int num = 0; num < v.size(); num++){
				v[num].candy = v[num].candx = -1;
				for (int i = 0; i < 4; i++){
					int ndir = (rev[v[num].dir] + 3 + i) % 4;
					int ny = v[num].y + dy[ndir], nx = v[num].x + dx[ndir];
					if (map[ny][nx] == '.' || map[ny][nx] == 'X'){
						v[num].candy = ny; v[num].candx = nx;
						v[num].dir = s[ndir];
						count[v[num].candy][v[num].candx]++;
						break;
					}
				}
			}
			
			for (int i = 0; i < h; i++){
				for (int j = 0; j < w; j++){
					if (count[i][j] > 1){
						int pos = -1, priority = 4;
						for (int num = 0; num < v.size(); num++){
							if (v[num].candy != i || v[num].candx != j) continue;
							int p = rev[v[num].dir];
							p = p < 2 ? (p + 2) : (p - 2);
							if (p < priority){
								pos = num; priority = p;
							}
						}
						
						moveIt(v, pos, i, j);
					}
				}
			}
			time++;
		}
		
		printf("NA\n");
		next:;
	}
	
	return (0);
}