题意：驴和老虎，在一个矩阵的两个格子里，有各自的起始方向。两者以相同的速度向前移动，前方不能走时驴总是向右，老虎总是向左。他们不能超出矩阵边界也不能走自己走过的格子（但可以走对方走过的格子）。如果不能前进时转向后仍不能前进则永久停止运动，问两者是否相遇（同时出现在同一个格子里，同时出现在格子的边界上不算），若相遇给出相遇坐标。
分析：模拟即可，每次将两者按其规则移动，并判断两者是否在同一个格子里。注意：起始点在同一个格子里也算相遇。转向不算时间，因为题里说二者速度始终相同。本来应该用面向对象的方式，但是比赛时不敢轻举妄动……
#include#include using namespace std;#define MAX_Y 1005#define MAX_X MAX_Ystruct Point{ int x, y; Point() {} Point(int x, int y):x(x), y(y) {} bool operator == (const Point &a) const { return a.x == x && a.y == y; } Point operator + (const Point &a) { return Point(x + a.x, y + a.y); }};Point dir[4] = {Point(0, 1), Point(1, 0), Point(0, -1), Point(-1, 0)};bool donkey_vis[MAX_X][MAX_Y];bool tiger_vis[MAX_X][MAX_Y];int tiger_dir;int donkey_dir;int grid_size;Point tiger, donkey;bool tiger_stop, donkey_stop;void visit(Point a, bool vis[][MAX_X]){ vis[a.x][a.y] = true;}void input(Point &a, int &dir){ int x, y; scanf("%d%d%d", &x, &y, &dir); a.x = x; a.y = y;}bool ok(Point a, bool vis[][MAX_Y]){ if (a.x < 0 || a.x >= grid_size || a.y < 0 || a.y >= grid_size) return false; return !vis[a.x][a.y];}void move(Point &animal, int &cur_dir, bool vis[][MAX_Y], bool &stop, int dir_delta){ if (stop) return; Point des = animal + dir[cur_dir]; if (ok(des, vis)) { animal = des; visit(des, vis); return; } cur_dir = (cur_dir + dir_delta + 4) % 4; des = animal + dir[cur_dir]; if (ok(des, vis)) { animal = des; visit(des, vis); return; } stop = true;}bool work(){ tiger_stop = false; donkey_stop = false; memset(tiger_vis, 0, sizeof(tiger_vis)); memset(donkey_vis, 0, sizeof(donkey_vis)); if (tiger == donkey) return true; visit(tiger, tiger_vis); visit(donkey, donkey_vis); while (!(tiger_stop && donkey_stop)) { move(tiger, tiger_dir, tiger_vis, tiger_stop, -1); move(donkey, donkey_dir, donkey_vis, donkey_stop, 1); if (tiger == donkey) return true; } return false;}int main(){ while (scanf("%d", &grid_size), grid_size) { input(donkey, donkey_dir); input(tiger, tiger_dir); if (work()) printf("%d %d\n", tiger.x, tiger.y); else printf("-1\n"); } return 0;}