ACM模版

描述


题解

这个题真的有趣，最短路，难点主要是在建图上~~~

这里先说一下题面的误区，我一开始理解为每盏灯只能点亮其所在的行或者列，谁成想并不是这样，而是说能点亮任何行或者列。那是否意味着我们需要考虑他和任何一行或者一列的边呢？实际上并不需要，因为题目中有一个很强的条件，当他要点亮一行或者一列时，前边点亮的就会熄灭，而人无时不刻都要待在光亮区域，所以呢？在每次点亮时，人都要在有灯的地方才行，酱紫的话，我们经过思考后，其实每次点亮时，都只有六个部分有价值，除去灯所在的行或者列外，剩下的四个就是灯所在的行或者列相邻的行或者列，这里我们将这些行或者列抽象为一个点，建边，权值为 1 ，反向建边，权值为 0 。这里我们有一个十分好的 hash 技巧，就是设一个 OFFSET 临界值，凡是等的位置，我们都按顺序默认为在 1∼OFFSET ，而行抽象的点映射到 OFFSET+1∼2∗OFFSET ，列抽象的点映射到 2∗OFFSET+1∼3∗OFFSET ，酱紫的话，我们建好图后直接一遍 dijkstra 算法即可，注意这里使用一下堆优化……不知道不用堆优化是否会爆了。

最短路好题，建图套路深！

代码

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <map>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
const int OFFSET = 1e4 + 10;
const int INF = 0x3f3f3f3f;
const int DIR[4][2] = {
  {
  0, 1}, {
  0, -1},
                       {
  1, 0}, {-1, 0}};

int cnt = 1;

struct edge
{
    int to, cost;
    edge() {}
    edge(int to_, int cost_) : to(to_), cost(cost_) {}
};

void add_edge(vector<edge> G[], int r, int c)
{
    G[cnt].push_back(edge(r + OFFSET, 1));
    G[cnt].push_back(edge(r + 1 + OFFSET, 1));
    G[cnt].push_back(edge(r - 1 + OFFSET, 1));
    G[cnt].push_back(edge(c + 2 * OFFSET, 1));
    G[cnt].push_back(edge(c + 1 + 2 * OFFSET, 1));
    G[cnt].push_back(edge(c - 1 + 2 * OFFSET, 1));

    G[r + OFFSET].push_back(edge(cnt, 0));
    G[r + 1 + OFFSET].push_back(edge(cnt, 0));
    G[r - 1 + OFFSET].push_back(edge(cnt, 0));
    G[c + 2 * OFFSET].push_back(edge(cnt, 0));
    G[c + 1 + 2 * OFFSET].push_back(edge(cnt, 0));
    G[c - 1 + 2 * OFFSET].push_back(edge(cnt, 0));
    cnt++;
}

int n, m, k;
int dis[MAXN];
int vis[MAXN];
pii p[MAXN];
vector<edge> E[MAXN];
map<pii, int> mpi;

void dijkstra(int s)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    priority_queue<pii, vector<pii>, greater<pii> > pq;

    dis[s] = 0;
    pq.push(pii(0, s));
    pii tmp;

    while (!pq.empty())
    {
        tmp = pq.top();
        pq.pop();
        int u = tmp.second;
        if (vis[u])
        {
            continue;
        }
        vis[u] = 1;
        for (int i = 0; i < E[u].size(); i++)
        {
            edge e = E[u][i];
            if (dis[e.to] > dis[u] + e.cost)
            {
                dis[e.to] = dis[u] + e.cost;
                pq.push(pii(dis[e.to], e.to));
            }
        }
    }
}

int main(int argc, const char * argv[])
{
    cin >> n >> m >> k;

    int r, c;
    for (int i = 1; i <= k; i++)
    {
        scanf("%d%d", &r, &c);
        add_edge(E, r, c);
        p[i] = make_pair(r, c);
        mpi[p[i]] = i;
    }

    pii t;
    for (int i = 1; i <= k; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            int x = p[i].first + DIR[j][0];
            int y = p[i].second + DIR[j][1];
            t = make_pair(x, y);
            if (mpi[t])
            {
                E[i].push_back(edge(mpi[t], 0));
            }
        }
    }

    t = make_pair(n, m);
    if (!mpi[t])
    {
        E[n + OFFSET].push_back(edge(k + 1, 0));
        E[m + 2 * OFFSET].push_back(edge(k + 1, 0));
    }

    dijkstra(mpi[pii(1, 1)]);

    int ans;
    if (mpi[t])
    {
        ans = dis[mpi[t]];
    }
    else
    {
        ans = dis[k + 1];
    }

    if (ans == INF)
    {
        ans = -1;
    }

    cout << ans << '\n';

    return 0;
}