2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 2) 解题报告



比赛链接

注 1：这场比赛 GYM 上的题号与题目上的不一样，这里以 GYM 内提交的题号为准
注 2：题目顺序为我个人提交的通过顺序，因为这场 GYM 是我一个人打的所以开题的顺序会比较奇怪

题目分析

A. Alphabet

因为可以在任意位置免费删除字符，并且添加字符也可以在任意位置进行。所以答案就是 26 - LIS(s) 。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

const int maxn = 55;

char s[maxn];
int dp[maxn];

int main() {
  scanf("%s", s + 1);
  int n = strlen(s + 1), ans = 0;
  FOR(i, 1, n) dp[i] = 1;
  FOR(i, 2, n) FOR(j, 1, i - 1) if (s[i] > s[j]) chkmax(dp[i], dp[j] + 1);
  FOR(i, 1, n) chkmax(ans, dp[i]);
  printf("%d", 26 - ans);
}


F. Equality

签到题。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

int a, b, c;

int main() {
  scanf("%d + %d = %d", &a, &b, &c);
  puts(a + b == c ? "YES" : "NO");
}


G. Gravity

模拟。不过我觉得可能有 O(n × m) 的做法？

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

const int maxn = 55;

char mat[maxn][maxn];
int n, m;

int main() {
  scanf("%d%d", &n, &m);
  FOR(i, 1, n) scanf("%s", mat[i] + 1);
  FOR(i, 1, m) {
    int en = n;
    ROF(j, n, 1) {
      if (mat[j][i] == '#') en = j - 1;
      else if (mat[j][i] == 'o')
        ROF(k, en, j + 1) if (mat[k][i] == '.') {
            swap(mat[k][i], mat[j][i]);
            break;
          }
    }
  }
  FOR(i, 1, n) printf("%s\n", mat[i] + 1);
}


K. Six Sides

暴力。因为每个骰子只有 6 个面，所以我们可以遍历所有可能的 6 × 6 种情况，用第一个人获胜的情况数除以非平局情况数就可以了。
但是这个题数据可能比较弱，因为按照题目的定义，我们要计算的是第一个人的获胜概率。如果两个骰子上 12 个面的所有数字都一样，这个游戏不会结束，所以第一个人也不会获胜？然而没有特判的提交也通过了。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

int d[2][6], cnt[2];

int main() {
  REP(i, 2) REP(j, 6) scanf("%d", &d[i][j]);
  REP(i, 6) REP(j, 6) {
      if (d[0][i] == d[1][j]) continue;
      if (d[0][i] > d[1][j]) cnt[0]++;
      cnt[1]++;
    }
  if (!cnt[1]) cnt[1]++;
  printf("%.5lf", double(cnt[0]) / cnt[1]);
}


M. Zigzag

动态规划。用 dp[i][0/1] 表示以 a[i] 结尾的 Zigzag 子序列其中最后一次更新是下降/上升的最大长度。于是原来的问题就被转化为两个独立的类 LIS 问题。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

const int maxn = 55;

int a[maxn], dp[maxn][2], n, ans;

int main() {
  scanf("%d", &n);
  FOR(i, 1, n) scanf("%d", a + i);
  FOR(i, 1, n) {
    dp[1][0] = dp[1][1] = 1;
    FOR(j, 1, i - 1){
      if (a[j] > a[i]) chkmax(dp[i][0], dp[j][1] + 1);
      if (a[j] < a[i]) chkmax(dp[i][1], dp[j][0] + 1);
    }
  }
  FOR(i, 1, n) REP(j, 2) chkmax(ans, dp[i][j]);
  printf("%d", ans);
}


H. Islands

这个题的难点在于如何把战争迷雾染成陆地或者是水域。如果把边界全部看成水域的话，对于任意一片战争迷雾，其可能的边界情况是：

  • 全部边界都是水域
  • 边界有水域有陆地
  • 全部边界都是陆地

显然对于第一种情况，我们希望这片战争迷雾完全是水域，不然会平添一个岛屿。对于后两种情况，如果把这片战争迷雾全部染色成陆地的话，无论如何不会增加新的岛屿。相反地，如果该战争迷雾与两片（或多片）本不连通的陆地邻接，那么这种染法可能会减少岛屿的个数。
染色以后搜索就可以了。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

const int maxn = 55;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

char mat[maxn][maxn];
int vis[maxn][maxn], clk, n, m;
bool flag[maxn * maxn];

void dfs1(int x, int y) {
  if (vis[x][y]) return;
  vis[x][y] = clk;
  REP(i, 4) {
    int nx = x + dx[i], ny = y + dy[i];
    if (mat[nx][ny] == 'L') flag[clk] = true;
    if (mat[nx][ny] == 'C') dfs1(nx, ny);
  }
}

void dfs2(int x, int y) {
  if (vis[x][y]) return;
  vis[x][y] = 1;
  REP(i, 4) {
    int nx = x + dx[i], ny = y + dy[i];
    if (mat[nx][ny] == 'L') dfs2(nx, ny);
  }
}

int main() {
  scanf("%d%d", &n, &m);
  reset(mat, 'W');
  FOR(i, 1, n) scanf("%s", mat[i] + 1);
  FOR(i, 1, n) FOR(j, 1, m) if (mat[i][j] == 'C' && !vis[i][j]) {
        clk++;
        dfs1(i, j);
      }
  FOR(i, 1, n) FOR(j, 1, m) if (flag[vis[i][j]]) mat[i][j] = 'L';
  reset(vis, 0);
  int ans = 0;
  FOR(i, 1, n) FOR(j, 1, m) if (mat[i][j] == 'L' && !vis[i][j]) {
        ans++;
        dfs2(i, j);
      }
  printf("%d", ans);
}


B. Barbells

暴力。因为 m 很小，不超过 14 ，所以子集生成或者 dfs 都可以处理出可能的杠铃片重量。然后再枚举杠铃杆即可。复杂度 O(m × 3m + mn × 2m) 。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

int b[15], p[15], n, m;
set<ll> lis, ans;

void dfs(int i, ll l, ll r) {
  if (i > m) return;
  if (l == r) lis.insert(r + l);
  dfs(i + 1, l + p[i + 1], r);
  dfs(i + 1, l, r + p[i + 1]);
  dfs(i + 1, l, r);
}

int main() {
  scanf("%d%d", &n, &m);
  FOR(i, 1, n) scanf("%d", b + i);
  FOR(i, 1, m) scanf("%d", p + i);
  dfs(0, 0, 0);
  FOR(i, 1, n) for (auto it : lis) ans.insert(it + b[i]);
  for (auto it : ans) printf("%lld\n", it);
}


E. Contest Score

用 std::multiset 模拟即可。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

const int maxn = 312;

int n, k, t[maxn];

int main() {
  scanf("%d%d", &n, &k);
  FOR(i, 1, n) scanf("%d", t + i);
  multiset<int> tt;
  FOR(i, 1, k) tt.insert(t[i]);
  ll ans = 0, pre = 0;
  while (!tt.empty()) {
    pre += *tt.begin();
    ans += pre;
    tt.erase(tt.find(*tt.begin()));
    if (k < n) tt.insert(t[++k]);
  }
  printf("%lld", ans);
}


D. Cameras

从前往后检查每个长度为 r 的窗口，滑动地维护窗口内的监控数目。如果发现当前窗口内的监控数目少于两个，那么贪心地从后往前把窗口内的监控数目补足两个即可。复杂度 O(n) 。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

const int maxn = 112345;

int k, r, n;
bool vis[maxn];

int main() {
  scanf("%d%d%d", &n, &k, &r);
  REP(i, k) {
    int p;
    scanf("%d", &p);
    vis[p] = true;
  }
  int cnt = 0, ans = 0;
  FOR(i, 1, r - 1) cnt += vis[i];
  FOR(i, r, n) {
    cnt -= vis[i - r];
    cnt += vis[i];
    ROF(j, i, 1) {
      if (cnt >= 2) break;
      if (vis[j]) continue;
      vis[j] = true;
      cnt++, ans++;
    }
  }
  printf("%d", ans);
}


L. Three Square

没有什么技巧性的暴力。比较恶心。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

pii lis[5];

int main() {
  int s = 0;
  REP(i, 3) {
    scanf("%d%d", &lis[i]._1, &lis[i]._2);
    if (lis[i]._1 < lis[i]._2) swap(lis[i]._1, lis[i]._2);
    s += lis[i]._1 * lis[i]._2;
  }
  int a = sqrt(s) + 0.5;
  if (a * a != s) {
    puts("NO");
    return 0;
  }
  sort(lis, lis + 3, greater<pii>());
  bool ok = false;
  if (lis[0]._1 == a) {
    int b = a - lis[0]._2;
    if (lis[1]._1 == lis[2]._1 && lis[1]._1 == a && lis[1]._2 + lis[2]._2 == b) 
      ok = true;
    else if (lis[1]._1 == lis[2]._1 && lis[1]._1 == b && lis[1]._2 + lis[2]._2 == a) 
      ok = true;
    else if (lis[1]._2 == lis[2]._2 && lis[1]._2 == b && lis[1]._1 + lis[2]._1 == a) 
      ok = true;
    else if (lis[1]._2 == lis[2]._1 && lis[1]._2 == b && lis[1]._1 + lis[2]._2 == a) 
      ok = true;
  }
  puts(ok ? "YES" : "NO");
}


I. Mismatched Socks

我们先找出最多的那种袜子，如果最多的袜子数量大于等于别的袜子的数量和，那么尽可能配对以后输出答案就可以了。如果小于，那么我们把最多的袜子放在左边，然后把其他袜子放在右边，之后尽可能地把右边的某种袜子全部移到左边但同时保证左边袜子数量不超过右边。这个过程结束后左边的任意一只袜子都和右边所有袜子的颜色不一样。之后我任意挑选右边的一种袜子，然后把它们尽可能移动到左边但保证左边袜子数量不超过右边。我们先用右边该颜色剩下的袜子与左边最多的袜子配对，一定可以把右边的这部分袜子用完。之后任意左右配对即可。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

const int maxn = 1123;

ll lis[maxn];
int n;

int main() {
  scanf("%d", &n);
  FOR(i, 1, n) scanf("%lld", &lis[i]);
  sort(lis + 1, lis + n + 1);
  ll mm = 0;
  FOR(i, 1, n - 1) mm += lis[i];
  if (mm <= lis[n]) printf("%lld", mm);
  else printf("%lld", mm + lis[n] >> 1);
}


J. Postman

首先很容易注意到我们无论何时均不应该在同一次投递过程中同时去原点左右两侧。因此，我们将原点两侧的信箱分开处理。对于某一侧，我们可以从远到近投递，如果某一次投递数量不足 K，那么我们可以顺便从远到近投递剩下的信箱，直到没有多余的背包空间或没有需要投递的信件方返程。复杂度 O(nlogn) 。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

int n, k;
ll ans;
priority_queue<pii> lis[2];

void solve(priority_queue<pii> &q) {
  while (!q.empty()) {
    auto now = q.top(); q.pop();
    int x = now._1, m = now._2;
    ans += m / k *  ll(x) * 2;
    m -= m / k * k;
    if (!m) continue;
    ans += 2 * x;
    int rem = k - m;
    while (rem && !q.empty()) {
      auto cur = q.top(); q.pop();
      if (rem >= cur._2) {
        rem -= cur._2;
        continue;
      }
      cur._2 -= rem;
      rem = 0;
      q.push(cur);
    }
  }
}

int main() {
  scanf("%d%d", &n, &k);
  FOR(i, 1, n) {
    int x, m;
    scanf("%d%d", &x, &m);
    if (!x) continue;
    if (x < 0) lis[0].push(mp(-x, m));
    else lis[1].push(mp(x, m));
  }
  solve(lis[0]);
  solve(lis[1]);
  printf("%lld", ans);
}


C. Buggy Robot

动态规划。用 dp[x][y][pos] 表示当前在网络内点 (x, y) 且将要执行第 pos 个指令时最少修改多少次。如果 pos 位置还有指令，那么可以用当前状态免费地遵循指令更新或者花费一次修改来删除该指令。在任意时候都可以花费一次修改来让机器人移动要邻接的合法位置。可以用类似于 Dijkstra 算法的方法来更新状态。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)

const int maxn = 55;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int dp[maxn][maxn][maxn], n, m, len;
char mat[maxn][maxn], cmd[maxn];

typedef pair<pii, pii> Node;

int main() {
  scanf("%d%d", &n, &m);
  FOR(i, 1, n) scanf("%s", mat[i] + 1);
  scanf("%s", cmd + 1);
  len = strlen(cmd + 1);
  reset(dp, 0x3f);
  int sx, sy, tx, ty;
  FOR(i, 1, n) FOR(j, 1, m) {
      if (mat[i][j] == 'R') sx = i, sy = j;
      if (mat[i][j] == 'E') tx = i, ty = j;
    }
  dp[sx][sy][1] = 0;
  set<Node> s;
  s.insert(mp(mp(0, 1), mp(sx, sy)));
  while (!s.empty()) {
    auto now = *s.begin(); s.erase(now);
    int used = now._1._1, pos = now._1._2, x = now._2._1, y = now._2._2;
    if (used > dp[x][y][pos]) continue;
    if (x == tx && y == ty) {
      printf("%d", used);
      return 0;
    }
    if (pos != len + 1) {
      int nx = x, ny = y, np = pos + 1;
      if (cmd[pos] == 'U' && nx != 1 && mat[nx - 1][ny] != '#') nx--;
      if (cmd[pos] == 'D' && nx != n && mat[nx + 1][ny] != '#') nx++;
      if (cmd[pos] == 'L' && ny != 1 && mat[nx][ny - 1] != '#') ny--;
      if (cmd[pos] == 'R' && ny != m && mat[nx][ny + 1] != '#') ny++;
      if (dp[nx][ny][np] > used) {
        dp[nx][ny][np] = used;
        s.insert(mp(mp(used, np), mp(nx, ny)));
      }
      if (dp[x][y][np] > used + 1) {
        dp[x][y][np] = used + 1;
        s.insert(mp(mp(used + 1, np), mp(x, y)));
      }
    }
    REP(i, 4) {
      int nx = x + dx[i], ny = y + dy[i];
      if (!nx) nx++;
      if (nx == n + 1) nx--;
      if (!ny) ny++;
      if (ny == m + 1) ny--;
      if (mat[nx][ny] == '#') nx -= dx[i], ny -= dy[i];
      if (dp[nx][ny][pos] > used + 1) {
        dp[nx][ny][pos] = used + 1;
        s.insert(mp(mp(used + 1, pos), mp(nx, ny)));
      }
    }
  }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 205,386评论 6赞 479
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,939评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,851评论 0赞 341
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,953评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,971评论 5赞 369
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,784评论 1赞 283
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,126评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,765评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,148评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,744评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,858评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,479评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,080评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,053评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,278评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,245评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,590评论 2赞 343