SOJ 4445 2015四川省赛模拟题

• 背景：赛场上就是因为没开这道题，而没拿到银，回来A了，感觉代码能力还是很弱，一定要先想好再敲，而且注重代码的函数化，这样无论是观感，还是调试都要好很多，逻辑要清晰，看代码要仔细，提交之前通读代码。
• 题意：起点在原点的frog，开始向右运动，且碰到障碍物就右转，问转多少次？
• 思路：关键是图的大小范围是$10^9$,无法存下，只有用类似链表的方法来存图。这里用了两个容器，一个以X为基准，一个一Y为基准，这两个容器设置很特殊，是为了满足题中特殊的查询需要：查询前进方向最近障碍物。

我的代码：

#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int LL;
const int M = 1009,INF = 0x3fffffff;
vector<pair<int, vector<int> > > vx, vy;
struct place {int x, y ,dir;}s;
vector<struct place> repeat;

bool operator == (struct place a, struct place b) {
    return a.x == b.x && a.y == b.y && a.dir == b.dir;
}

void input(int n) {
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        bool key = true;
        for (int j = 0; j < vx.size(); j++) {
            if (vx[j].first == x) {
                vx[j].second.push_back(y);
                key = false;
                break;
            }
        }
        if (key) {
            pair<int, vector<int> >p;
            p.first = x;
            p.second.push_back(y);
            vx.push_back(p);
        }
        key = true;
        for (int j = 0; j < vy.size(); j++) {
            if (vy[j].first == y) {
                vy[j].second.push_back(x);
                key = false;
                break;
            }
        }
        if (key) {
            pair<int, vector<int> >p;
            p.first = y;
            p.second.push_back(x);
            vy.push_back(p);
        }
    }
}

bool move(void) {
    if (s.dir == 0) {
        for (int i = 0; i < vy.size(); i++) {
            if (vy[i].first == s.y) {
                int temp = INF;
                bool ok = false;
                for (int j = 0; j < vy[i].second.size(); j++) {
                    if(vy[i].second.at(j) > s.x && vy[i].second.at(j) < temp) {
                        temp = vy[i].second.at(j);
                        ok = true;
                    }
                }
                s.x = temp - 1;
                s.dir = 1;
                return ok;
            }
        }
    }
    if (s.dir == 1) {
        for (int i = 0; i < vx.size(); i++) {
            if (vx[i].first == s.x) {
                int temp = -INF;
                bool ok = false;
                for (int j = 0; j < vx[i].second.size(); j++) {
                    if(vx[i].second.at(j) < s.y && vx[i].second.at(j) > temp) {
                        temp = vx[i].second.at(j);
                        ok = true;
                    }
                }
                s.y = temp + 1;
                s.dir = 2;
                return ok;
            }
        }
    }
    if (s.dir == 2) {
        for (int i = 0; i < vy.size(); i++) {
            if (vy[i].first == s.y) {
                int temp = -INF;
                bool ok = false;
                for (int j = 0; j < vy[i].second.size(); j++) {
                    if(vy[i].second.at(j) < s.x && vy[i].second.at(j) > temp) {
                        temp = vy[i].second.at(j);
                        ok = true;
                    }
                }
                s.x = temp + 1;
                s.dir = 3;
                return ok;
            }
        }
    }
    if (s.dir == 3) {
        for (int i = 0; i < vx.size(); i++) {
            if (vx[i].first == s.x) {
                int temp = INF;
                bool ok = false;
                for (int j = 0; j < vx[i].second.size(); j++) {
                    if(vx[i].second.at(j) > s.y && vx[i].second.at(j) < temp) {
                        temp = vx[i].second.at(j);
                        ok = true;
                    }
                }
                s.y = temp - 1;
                s.dir = 0;
                return ok;
            }
        }
    }
    return false;
}

bool judge_infinite(void) {
    for (int i = 0; i < repeat.size(); i++) {
        if (s == repeat[i]) return true;
    }
    return false;
}

int main(void) {
    //problem: soj4445, address:http://acm.scu.edu.cn/soj/problem.action?id=4445
    int n;
    while (~scanf("%d", &n)) {
        vx.clear();
        vy.clear();
        repeat.clear();
        input(n);
        s.x = s.y = s.dir = 0;
        for (int i = 0;; i++) {
            repeat.push_back(s);
            if (!move()) {
                printf("%d\n", i);
                break;
            }
            if (judge_infinite()) {
                printf("-1\n");
                break;
            }
        }
    }
    return 0;
}