ACM-Training Record Always_Penalty 搜索
0. 照例先bb幾句
不會搜索題……好毒瘤啊……這種時候就應該甩鍋給隊友
調了一部分題目做（全做完實在是做不動），後面的Max-Min搜索以及它的Alpha-beta剪枝不會
A. 棋盤問題
1321 -- 棋盤問題
題意：有障礙的類八皇后問題
題解：無腦回溯，記得把障礙也標記出來即可
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 10
using namespace std;
char board[maxn][maxn];
int vis[maxn];
int n, k, ans;
inline void dfs(int cur, int step)
{
if(step == k){
ans++;
return ;
}
if(cur > n) return ;
for(int i = 1; i <= n; i++){
if(board[cur][i] == # && !vis[i]){
vis[i] = 1;
dfs(cur+1, step+1);
vis[i] = 0;
}
}
dfs(cur+1, step);
return;
}
int main()
{
while(scanf("%d%d", &n, &k) == 2 && n != -1 && k != -1){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf(" %c", &board[i][j]);
ans = 0;
memset(vis, 0, sizeof(vis));
dfs(1, 0);
printf("%d
", ans);
}
return 0;
}
B. Catch That Cow
Problem - 2717
題意：從數軸上一點走到另一點，每次可以走到 ，問最少需要幾步
題解：一開始敲了一個dfs，然後喜聞樂見地死循環了，然後考慮建圖做最短路，發現還不如直接bfs
#include <cstdio>
#include <cstring>
#include <queue>
#define N 100100
using namespace std;
int n, k, ret;
int d[N << 1];
inline int bfs(int s, int t)
{
memset(d, 0, sizeof(d)); bool vis[N << 1] = {0};
queue<int> q; q.push(s); d[s] = 0; vis[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == t) return d[t];
for (int i = 0; i < 3; ++i) {
int v;
if (i == 0) v = u + 1;
else if (i == 1) v = u - 1;
else if (i == 2) v = u << 1;
if (v < 0 || v > 200000) continue;
if (vis[v]) continue;
vis[v] = 1; d[v] = d[u] + 1; q.push(v);
}
}
}
int main()
{
//freopen("test.in", "r", stdin);
scanf("%d%d", &n, &k);
//if (n > k) swap(n, k);
printf("%d", bfs(n, k));
return 0;
}
WA了8次，嗯，Always_Penalty
C. Fliptile
3279 -- Fliptile
題意：把 翻轉以後它周圍的四個（如果有）位置會一起翻轉，問把原狀態翻轉成全部為0最少需要幾步
題解：先枚舉第一行的狀態，然後計算剩下的。一個位置是1，當且僅當周圍的格子的和是奇數
#include <cstdio>
#define N 18
#define INF 0x3f3f3f3f
using namespace std;
struct Grid {
int grid[N][N];
} g[3];
int m, n, ret = INF;
inline bool check(Grid& src, Grid& g, int x, int y) {
return (src.grid[x][y] + g.grid[x][y] +
g.grid[x - 1][y] + g.grid[x][y - 1] +
g.grid[x + 1][y] + g.grid[x][y + 1]) & 1;
}
inline int dfs(Grid& src, Grid& g) {
int ret = 0;
for (int i = 2; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (check(src, g, i - 1, j)) g.grid[i][j] = 1;
for (int i = 1; i <= n; ++i) if (check(src, g, m, i)) return -1;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
ret += g.grid[i][j];
return ret;
}
int main()
{
//freopen("test.in", "r", stdin);
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
scanf("%d", &g[0].grid[i][j]);
for (int s = 0; s < (1 << n); ++s) {
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
g[1].grid[i][j] = 0;
for (int i = 1; i <= n; ++i)
if (s & (1 << (i - 1))) g[1].grid[1][i] = 1;
int tmp = dfs(g[0], g[1]);
if (tmp == -1) continue;
if (tmp < ret) {
ret = tmp;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
g[2].grid[i][j] = g[1].grid[i][j];
}
}
if (ret == INF) return printf("IMPOSSIBLE"), 0;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
printf("%d%c", g[2].grid[i][j], j == n ?
: );
return 0;
}
D. Find The Multiple
1426 -- Find The Multiple
題意：找一個僅有0和1組成的正整數，使得它是n的倍數
題解：經過dfs發現其實最小的答案並不會很大，所以就像二叉樹那樣來枚舉二進位
#include <cstdio>
#include <cstring>
#include <vector>
#define N 1000100
using namespace std;
typedef long long ll;
int n;
ll v[N];
int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d", &n) == 1 && n) {
v[0] = 0;
for (int i = 1; ; ++i) {
v[i] = (v[i >> 1] << 1) + (v[i >> 1] << 3) + (i & 1);
if (v[i] % n == 0) {
printf("%lld
", v[i]);
break;
}
}
}
return 0;
}
E. Dungeon Master
2251 -- Dungeon Master
（小聲bb）題目名字好評（ah♂Thank you sir）
題意：Van様有一個地♂牢，而他是這個地牢的主人。現在反抗♂的平家boy想要逃出這個地牢
題解：三維的話也就是再加一個 軸上的增量
#include <cstdio>
#include <cstring>
#include <queue>
#define N 50
#define INF 0x3f3f3f3f
using namespace std;
const int dx[] = {-1, 1, 0, 0, 0, 0};
const int dy[] = {0, 0, -1, 1, 0, 0};
const int dz[] = {0, 0, 0, 0, -1, 1};
struct Point {
int x, y, z;
Point() {}
Point(const int& x, const int& y, const int& z) : x(x), y(y), z(z) {}
bool operator == (const Point& p) { return x == p.x && y == p.y && z == p.z; }
} op, ed;
int L, R, C, d[N][N][N];
char mp[N][N][N];
inline int bfs(Point s, Point t)
{
queue<Point> q; q.push(s);
int sx = s.x, sy = s.y, sz = s.z;
d[sx][sy][sz] = 0;
while (!q.empty()) {
Point p = q.front(); q.pop();
int x = p.x, y = p.y, z = p.z;
if (p == t) return d[x][y][z];
for (int i = 0; i < 6; ++i) {
int nx = x + dx[i], ny = y + dy[i], nz = z + dz[i];
if (nx >= 1 && nx <= L && ny >= 1 && ny <= R && nz >= 1 && nz <= C) {
if (d[nx][ny][nz] != -1 || d[nx][ny][nz] == INF) continue;
d[nx][ny][nz] = d[x][y][z] + 1;
Point v = Point(nx, ny, nz);
if (v == t) return d[nx][ny][nz];
q.push(v);
}
}
}
return -1;
}
int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d%d%d", &L, &R, &C) == 3 && L && R && C) {
memset(d, -1, sizeof(d));
for (int i = 1; i <= L; ++i)
for (int j = 1; j <= R; ++j)
scanf("%s", mp[i][j] + 1);
for (int i = 1; i <= L; ++i)
for (int j = 1; j <= R; ++j)
for (int k = 1; k <= C; ++k) {
if (mp[i][j][k] == #) d[i][j][k] = INF;
if (mp[i][j][k] == S) op = Point(i, j, k);
if (mp[i][j][k] == E) ed = Point(i, j, k);
}
int ret = bfs(op, ed);
if (ret == -1) puts("Trapped!");
else printf("Escaped in %d minute(s).
", ret);
}
return 0;
}
F. Pots
3414 -- Pots
題意：兩個沒有刻度的杯子可以互相倒水，問能不能量出給定的體積
題解：bfs，兩個杯子各自的水量作為狀態。記錄路徑的話記錄一下fa結點就行了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#define N 110
using namespace std;
struct Node {
int v[2], d;
string opt;
Node *fa;
Node() { fa = NULL; }
};
inline void print(Node *o) {
cout << o -> d << endl;
stack<string> s;
for (; o -> fa; o = o -> fa) s.push(o -> opt);
for (; !s.empty(); s.pop()) cout << s.top() << endl;
}
int a, b, c, vis[N][N];
inline bool bfs(int a, int b, int c)
{
queue<Node*> q;
Node *s = new Node();
s -> v[0] = s -> v[1] = s -> d = 0; s -> opt = "";
q.push(s); vis[0][0] = 1;
while (!q.empty()) {
Node *u = q.front(); q.pop();
if (u -> v[0] == c || u -> v[1] == c) return print(u), 1;
for (int i = 0; i < 6; ++i) {
Node *v = new Node();
if (i == 0) {
v -> v[0] = a;
v -> v[1] = u -> v[1];
v -> opt = "FILL(1)";
} else if (i == 1) {
v -> v[0] = u -> v[0];
v -> v[1] = b;
v -> opt = "FILL(2)";
} else if (i == 2) {
if (u -> v[0] == 0) continue;
v -> v[0] = 0;
v -> v[1] = u -> v[1];
v -> opt = "DROP(1)";
} else if (i == 3) {
if (u -> v[1] == 0) continue;
v -> v[0] = u -> v[0];
v -> v[1] = 0;
v -> opt = "DROP(2)";
} else if (i == 4) {
if (u -> v[0] == 0) continue;
if (u -> v[0] > b - u -> v[1]) {
v -> v[0] = u -> v[0] - b + u -> v[1];
v -> v[1] = b;
} else {
v -> v[0] = 0;
v -> v[1] = u -> v[0] + u -> v[1];
}
v -> opt = "POUR(1,2)";
} else if (i == 5) {
if (u -> v[1] == 0) continue;
if (u -> v[1] > a - u -> v[0]) {
v -> v[0] = a;
v -> v[1] = u -> v[1] - a + u -> v[0];
} else {
v -> v[0] = u -> v[0] + u -> v[1];
v -> v[1] = 0;
}
v -> opt = "POUR(2,1)";
}
if (vis[v -> v[0]][v -> v[1]]) continue;
vis[v -> v[0]][v -> v[1]] = 1; v -> d = u -> d + 1;
v -> fa = u; q.push(v);
}
}
return 0;
}
int main()
{
//freopen("test.in", "r", stdin);
cin >> a >> b >> c;
int ret = bfs(a, b, c);
if (!ret) cout << "impossible" << endl;
return 0;
}
G. Fire!
Fire! - UVA 11624 - Virtual Judge
題意：逃出火場
題解：先對火bfs一次，然後再從人開始bfs，，，這道題不止一個火
#include <cstdio>
#include <cstring>
#include <queue>
#define N 1010
using namespace std;
typedef pair<int, int> pt;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int T, R, C, d[N][N], fire[N][N];
char mp[N][N];
pt J;
inline void bfs1()
{
queue<pt> q; memset(fire, -1, sizeof(fire));
for (int i = 1; i <= R; ++i)
for (int j = 1; j <= C; ++j)
if (mp[i][j] == F) {
fire[i][j] = 0;
q.push(pt(i, j));
}
while (!q.empty()) {
pt p = q.front(); q.pop();
int x = p.first, y = p.second;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
if (mp[nx][ny] == #) continue;
if (fire[nx][ny] != -1) continue;
fire[nx][ny] = fire[x][y] + 1;
q.push(pt(nx, ny));
}
}
}
inline int bfs2(pt s)
{
queue<pt> q; memset(d, -1, sizeof(d));
d[s.first][s.second] = 0; q.push(s);
while (!q.empty()) {
pt p = q.front(); q.pop();
int x = p.first, y = p.second;
if (x == 1 || x == R || y == 1 || y == C) return d[x][y] + 1;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
if (mp[nx][ny] == #) continue;
if (d[nx][ny] != -1) continue;
if (fire[nx][ny] != -1 && fire[nx][ny] <= d[x][y] + 1) continue;
d[nx][ny] = d[x][y] + 1;
q.push(pt(nx, ny));
}
}
return -1;
}
int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d%d", &R, &C);
for (int i = 1; i <= R; ++i) scanf("%s", mp[i] + 1);
for (int i = 1; i <= R; ++i)
for (int j = 1; j <= C; ++j)
if (mp[i][j] == J) J = pt(i, j);
bfs1();
int ret = bfs2(J);
if (ret == -1) puts("IMPOSSIBLE");
else printf("%d
", ret);
}
return 0;
}
V. 找環
[NWPU2018]萌新第二次上課作業-簡單搜索 - Virtual Judge
我也不知道這是UVa的第幾題
題意：找環，一個環的定義是環裏的每個點都至少在兩個方向上和環裏的其他點相鄰
題解：無腦dfs
#include <cstdio>
#include <cstring>
#define N 110
#define INF 0x3f3f3f3f
using namespace std;
const int dx[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, -1, 1, -1, 1, 1, -1};
int m, n, ret, vis[N][N];
char mp[N][N];
inline void dfs(int x, int y, int prex, int prey)
{
vis[x][y] = 1;
for (int d = 0; d < 8; ++d) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 1 && nx <= m && ny >= 1 && ny <= n) {
if (mp[nx][ny] == .) continue;
if (vis[nx][ny]) {
if (nx == prex && ny == prey) continue;
++ret;
continue;
}
dfs(nx, ny, x, y);
}
}
}
int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d%d", &m, &n) == 2) {
ret = 0; memset(vis, 0, sizeof(vis));
for (int i = 1; i <= m; ++i)
scanf("%s", mp[i] + 1);
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) {
if (mp[i][j] == .) continue;
if (vis[i][j]) continue;
dfs(i, j, i, j);
}
printf("%d
", ret / 2);
}
return 0;
}
1. 後記
偷懶了……好菜啊……
推薦閱讀：
