搜索小练#2

Posted on Edited on In

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstring>
#include <queue>
#define N 110
using namespace std;

int l, r, c, sx, sy, sz;
char a[N][N][N];
int vis[N][N][N];

struct node {int x, y, z, cnt;};
int dir[6][3] = {{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}};
inline void bfs () {
    queue<node>Q; node t;
    vis[sx][sy][sz] = 1;
    t.x = sx, t.y = sy, t.z = sz, t.cnt = 0;
    Q.push (t);
    while (Q.size()) {
        node nows = Q.front(); Q.pop();
        int nx = nows.x, ny = nows.y, nz = nows.z, ncnt = nows.cnt;
        if (a[nx][ny][nz] == 'E') {cout << "Escaped in "<< ncnt <<" minute(s)."<< '\n';return;}
        for (int i = 0; i < 6; ++ i) {
            node T;
            T.x = nx + dir[i][0], T.y = ny + dir[i][1], T.z = nz + dir[i][2];
            T.cnt = ncnt + 1;
            if (T.x > l || T.y > r || T.z > c || T.x < 1 || T.y < 1 || T.z < 1) continue;
            if (a[T.x][T.y][T.z] != '#' && !vis[T.x][T.y][T.z]) {
                vis[T.x][T.y][T.z] = 1;
                Q.push (T);
            }
        }
    }
    cout << "Trapped!\n";
}
int main () {
    while (cin >> l >> r >> c) {
        if (l == 0 && r == 0 && c == 0) break;
        memset (vis, 0, sizeof vis);
        for (int i = 1; i <= l; ++ i)
            for (int j = 1; j <= r; ++ j)
                for (int k = 1; k <= c; ++ k) {
                    cin >> a[i][j][k];
                    if (a[i][j][k] == 'S') sx = i, sy = j, sz = k;
                }
        bfs ();
    }
    return 0;
}
/*
3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0
*/

PS:

1>\(debug\)完记得清理干净

2>遇到bfs就写队列

3>模拟三维的方向：

1
int dir[6][3] = {{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}};

第二次写这道题的时候，很明显的吃力，太久没有温习编程知识了，什么queue，bfs都记不清了

我知道这是一道很蠢的板子题，但是如果不会做，蠢的就是我了吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 32;

int L, R, C, sx, sy, sz;
char a[N][N][N];
int vis[N][N][N];

struct node {int x, y, z, cnt;};
int dir[6][3] = {{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}};

inline void bfs()
{
	queue<node>Q; node t;
	vis[sx][sy][sz] = 1;
	t.x = sx, t.y = sy, t.z = sz, t.cnt = 0;
	Q.push(t);
	while (Q.size())
	{
		node nows = Q.front(); Q.pop();
		int nx = nows.x, ny = nows.y, nz = nows.z, ncnt = nows.cnt;
		if (a[nx][ny][nz] == 'E')
		{
			cout << "Escaped in " << ncnt << " minute(s)." << '\n';
			return;
		}
		for (int i = 0; i < 6; ++ i)
		{
			node T;
			T.x = nx + dir[i][0], T.y = ny + dir[i][1], T.z = nz + dir[i][2];
			T.cnt = ncnt + 1;
			if (T.x > L || T.y > R || T.z > C || T.x < 1 || T.y < 1 || T.z < 1) continue;
			if (a[T.x][T.y][T.z] != '#' && ! vis[T.x][T.y][T.z])
			{
				vis[T.x][T.y][T.z] = 1;
				Q.push(T);
			}
		}
	}
	puts("Trapped!");
	return;
}

signed main()
{
	while (scanf ("%d%d%d", &L, &R, &C))
	{
		if (L == 0 && R == 0 && C == 0) return 0;
		int k, i, j;
		memset(vis, 0, sizeof vis);
		for (k = 1; k <= L; ++ k)
		{
			for (i = 1; i <= R; ++ i)
			{
				for (j = 1; j <= C; ++ j)
				{
					//scanf ("%c", &a[k][i][j]);
					cin >> a[k][i][j];
					if (a[k][i][j] == 'S') sx = k, sy = i, sz = j;
				}
			}
		}
		//cout << sx << ' ' << sy << ' ' << sz << '\n';
		bfs();
	}
	return 0;
}

/*
3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0
*/