广搜好难/kk
P1162 填涂颜色
在原矩阵外再围一层 (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 马的遍历
广搜标记步数即可，像是个变异的最短路（大雾）。
注意厂宽。
#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
", dis[t] == inf ? -1 : dis[t]);
return 0;
}
P1032 字串变换
随 便 错
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
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, ans;
map <string, int> vis;
string a, b, from[10], to[10];
struct node { string str; int cnt; };
string change(string str, int i, int j) {
string ans = "";
if (i + from[j].size() > str.size()) return ans;
for (int k = 0; k < from[j].size(); k++)
if (str[i + k] != from[j][k]) return ans;
ans = str.substr(0, i);
ans += to[j];
ans += str.substr(i + from[j].size());
return ans;
}
void bfs() {
queue <node> Q;
Q.push((node){a, 0});
while (!Q.empty()) {
node x = Q.front();
Q.pop();
string now;
if (vis.count(x.str) == 1) continue;
if (x.str == b) {
ans = x.cnt;
break;
}
vis[x.str] = 1;
for (int i = 0; i < x.str.size(); i++) {
for (int j = 0; j < n; j++) {
now = change(x.str, i, j);
if (now != "") {
Q.push((node){now, x.cnt + 1});
}
}
}
}
}
int main() {
cin >> a >> b;
int tot = 0;
while (cin >> from[tot] >> to[tot]) tot++;
n = tot;
bfs();
if (ans > 10 || ans == 0) puts("NO ANSWER!");
else cout << ans << '
';
return 0;
}
P1126 机器人搬重物
题意有点坑。。
只有一个地方用了米的描述，其他地方全都是步，所以导致无法透彻理解题意。
看了题解才明白不能走最外侧的格子，因为机器人有宽度（大雾，你也没说格子的边长啥的啊，题意太不准确了吧……
一个坑点就是机器人走的是格点，而障碍是格子，格子的四个点都不能走。
还有就是第一次访问这个点并不一定是访问这个点的最小路径，因为最多可以走三步（调了很久……），所以可以记一个 (dis) 数组，如果目前的步数小于到当前点的 (dis)，一样应该加入队列中。
注意走 (1,2,3) 步的花费都是 (1)，想达到自己想转到的方向的最大花费其实是 (2)。
（写了个一百多行的大暴搜啊）
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 66;
const int dx[13] = {0, -1, 0, 1, 0, -2, 0, 2, 0, -3, 0, 3, 0};
const int dy[13] = {0, 0, 1, 0, -1, 0, 2, 0, -2, 0, 3, 0, -3};
const int diss[5][5] = {{0,0,0,0,0},{0,0,1,2,1},{0,1,0,1,2},{0,2,1,0,1},{0,1,2,1,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, m, a[A][A], dis[A][A], ans = 0x3f3f3f3f;
int sx, sy, tx, ty, sdir, vis[A][A];
struct node { int x, y, dir, cnt; };
inline void bbffss() {
queue <node> Q;
memset(dis, 0x3f, sizeof(dis));
Q.push((node){sx, sy, sdir, 0});
dis[sx][sy] = 0, vis[sx][sy] = 1;
while (!Q.empty()) {
node tmp = Q.front(); Q.pop();
int x = tmp.x, y = tmp.y, cnt = tmp.cnt, dir = tmp.dir;
if (x == tx && y == ty) {
ans = min(ans, cnt);
continue;
}
for (int i = 1; i <= 12; i++) {
int bx = x + dx[i], by = y + dy[i];
int nowdir = (i % 4);
if (nowdir == 0) nowdir = 4;
int change = diss[dir][nowdir];
if (i >= 1 && i <= 4) {
if (bx >= 1 && bx <= n && by >= 1 && by <= m && (!vis[bx][by] || cnt + 1 + change < dis[bx][by]) && a[bx][by] != 1) {
Q.push((node){bx, by, nowdir, cnt + 1 + change});
dis[bx][by] = cnt + 1 + change, vis[bx][by] = 1;
}
}
else if (i >= 5 && i <= 8) {
int flag = 0;
if (x != bx) {
int minn = min(x, bx), maxn = max(x, bx);
for (int k = minn; k <= maxn; k++) {
if (a[k][by]) { flag = 1; break; }
}
}
if (y != by) {
int minn = min(y, by), maxn = max(y, by);
for (int k = minn; k <= maxn; k++) {
if (a[bx][k]) { flag = 1; break; }
}
}
if (flag) continue;
if (bx >= 1 && bx <= n && by >= 1 && by <= m && (!vis[bx][by] || cnt + 1 + change < dis[bx][by])) {
Q.push((node){bx, by, nowdir, cnt + 1 + change});
dis[bx][by] = cnt + 1 + change, vis[bx][by] = 1;
}
}
else if (i >= 9 && i <= 12) {
int flag = 0;
if (x != bx) {
int minn = min(x, bx), maxn = max(x, bx);
for (int k = minn; k <= maxn; k++){
if (a[k][by]) { flag = 1; break; }
}
}
if (y != by) {
int minn = min(y, by), maxn = max(y, by);
for (int k = minn; k <= maxn; k++){
if (a[bx][k]) { flag = 1; break; }
}
}
if (flag) continue;
if (bx >= 1 && bx <= n && by >= 1 && by <= m && (!vis[bx][by] || cnt + 1 + change < dis[bx][by])) {
Q.push((node){bx, by, nowdir, cnt + 1 + change});
dis[bx][by] = cnt + 1 + change, vis[bx][by] = 1;
}
}
}
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = read();
if (a[i][j] == 1)
a[i - 1][j - 1] = 1, a[i - 1][j] = 1, a[i][j - 1] = 1;
}
}
for (int i = 1; i <= n; i++) a[i][0] = a[i][m] = 1;
for (int i = 0; i <= m; i++) a[0][i] = 1, a[n][i] = 1;
sx = read(), sy = read(), tx = read(), ty = read();
char s;
cin >> s;
if (s == 'N') sdir = 1;
else if (s == 'E') sdir = 2;
else if (s == 'S') sdir = 3;
else if (s == 'W') sdir = 4;
bbffss();
printf("%d", ans == 0x3f3f3f3f ? -1 : ans);
return 0;
}