广搜好难/kk

P1162 填涂颜色

link

在原矩阵外再围一层 \(2\)，方便能够从边界搜索。

把输入数据中的 \(0\) 全都换成 \(2\)，然后再处理在封闭圈外的 \(2\)，将其变成 \(0\)。

#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int A = 111;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

inline int read() {
  char c = getchar(); int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

int n, a[A][A], vis[A][A];
struct node { int x, y; };

void bfs() {
  queue <node> Q;
  Q.push((node){0, 0});
  a[0][0] = 0, vis[0][0] = 1;
  while (!Q.empty()) {
    int x = Q.front().x, y = Q.front().y;
    Q.pop();
    for (int i = 0; i < 4; i++) {
      int bx = x + dx[i], by = y + dy[i];
      if (bx >= 0 && bx <= n + 1 && by >= 0 && by <= n + 1 && !vis[bx][by] && a[bx][by] != 1) {
        if (a[bx][by] == 2) {
          vis[bx][by] = 1, a[bx][by] = 0;
          Q.push((node){bx, by});
        }  
      }
    }
  }
  return;
}

int main() {
  n = read();
  for (int i = 0; i <= n + 1; i++) a[0][i] = 2;
  for (int i = 0; i <= n + 1; i++) a[n + 1][i] = 2;
  for (int i = 1; i <= n; i++) {
    a[i][0] = a[i][n + 1] = 2;
    for (int j = 1; j <= n; j++) {
      a[i][j] = read();
      if (a[i][j] == 0) a[i][j] = 2;
    }
  }
  bfs();
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cout << a[i][j] << " ";
    }
    puts("");
  }
  return 0;
}

P1443 马的遍历

link

广搜标记步数即可，像是个变异的最短路（大雾）。

注意厂宽。

#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int A = 4e2 + 11;
const int inf = 0x3f3f3f3f;
const int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

inline int read() {
  char c = getchar(); int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

struct node { int x, y; };
int n, m, sx, sy, vis[A][A], dis[A][A];

int main() {
  n = read(), m = read(), sx = read(), sy = read();
  queue <node> Q;
  memset(dis, inf, sizeof(dis));
  Q.push((node){sx, sy});
  dis[sx][sy] = 0, vis[sx][sy] = 1;
  while (!Q.empty()) {
    int x = Q.front().x, y = Q.front().y;
    Q.pop(), vis[x][y] = 0;
    for (int i = 0; i < 8; i++) {
      int bx = x + dx[i], by = y + dy[i];
      if (bx < 1 || bx > n || by < 1 || by > m) continue;
      if (dis[x][y] + 1 < dis[bx][by]) {
        dis[bx][by] = dis[x][y] + 1;
        if (!vis[bx][by]) vis[bx][by] = 1, Q.push((node){bx, by});
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      printf("%-5d", dis[i][j] == inf ? -1 : dis[i][j]);
    }
    puts("");
  }
  return 0;
}

P3956 棋盘

直接跑最短路，广搜有点麻烦/kk。

#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int A = 1e3 + 11;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar(); int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

int flag, s, t, n, m;
int vis[A], e[A][A], x[A], y[A], w[A], dis[A];

struct node {
  int x, y;
  bool operator < (const node &b) const {
    return y > b.y;
  }
};
priority_queue <node> Q;

inline void Dij() {
  memset(dis, inf, sizeof(dis));
  Q.push((node){s, 0});
  dis[s] = 0, vis[s] = 1;
  while (!Q.empty()) {
    int x = Q.top().x; Q.pop(), vis[x] = 0;
    for (int i = 1; i <= m; i++) 
      if (dis[x] + e[x][i] < dis[i]) {
        dis[i] = e[x][i] + dis[x];
        if (!vis[i]) vis[i] = 1, Q.push((node){i, dis[i]});
      }
  }
}

int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; i++) {
    x[i] = read(), y[i] = read(), w[i] = read();
    if (x[i] == 1 && y[i] == 1) s = i;
    if (x[i] == n && y[i] == n) flag = 1, t = i;
  }
  if (!flag) x[m + 1] = n, y[m + 1] = n, t = m + 1;
  memset(e, inf, sizeof(e));
  for (int i = 1; i <= m; i++) {
    for (int j = i + 1; j <= m; j++) {
      if (abs(x[i] - x[j]) + abs(y[i] - y[j]) == 1) 
        e[i][j] = e[j][i] = abs(w[i] - w[j]);
      if (abs(x[i] - x[j]) + abs(y[i] - y[j]) == 2) 
        e[i][j] = e[j][i] = 2 + abs(w[i] - w[j]);        
    }
  }
  if (!flag) {
    for (int i = 1; i <= m; i++)
      if (abs(x[i] - x[t]) + abs(y[i] - y[t]) == 1)
        e[i][t] = e[t][i] = 2;
    m++;
  }
  Dij();
  printf("%d\n", dis[t] == inf ? -1 : dis[t]);
  return 0;
}

P1032 字串变换

link

P1126 机器人搬重物

link