Welcome to my blog!

Posted on Edited on In

题目

thought:

1.make two queue, one is for J, another is for F

2.first update the J,and then uodate the F

the code is follow:

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
#include <bits/stdc++.h>
using namespace std;
//我一定要去寻找，就算无尽的星辰令我的探寻希望渺茫，就算我必须单枪匹马
const int N = 1e3+66;

int n, m, T;
int vis[N][N];
char ch[N][N];

int dx[5] = {0, 0, 1, -1};
int dy[5] = {1, -1, 0, 0};

struct node {int x, y;node(int x, int y):x(x), y(y){}};

inline void bfs () {
    queue<node>jq, fq;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j) {
            if (ch[i][j] == 'J') {
                jq.push(node(i, j));
                vis[i][j] = 1;
            } else if (ch[i][j] == 'F') {
                fq.push(node(i, j));
                ch[i][j] = '#';
            }
        }
    
    int step(0);
    while (jq.size()) {
        ++ step;
        for (int i = 0, j = jq.size(); i < j; ++ i) {
            node tmp = jq.front(); jq.pop();
            if (ch[tmp.x][tmp.y] == '#') continue;
            for (int k = 0; k < 4; ++ k) {
                int nx = tmp.x+dx[k], ny = tmp.y+dy[k];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (ch[nx][ny] != '#' && !vis[nx][ny])
                        vis[nx][ny] = 1, jq.push(node(nx, ny));
                }
                else {cout << step << '\n'; return;}
            }
        }
        for (int i = 0, j = fq.size(); i < j; ++ i) {
            node tmp = fq.front(); fq.pop();
            for (int k = 0; k < 4; ++ k) {
                int nx = tmp.x+dx[k], ny = tmp.y+dy[k];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && ch[nx][ny] != '#')
                    ch[nx][ny] = '#', fq.push(node(nx, ny));
            }
        }
    }
    puts ("IMPOSSIBLE");
}

int main () {
    cin >> T;
    while (T --> 0) {
        cin >> n >> m;
        for (int i = 0; i < n; ++ i) scanf ("%s", ch[i]);
        bfs ();
        memset (vis, 0, sizeof vis);
    }
    return 0;
}

Posted on Edited on In

题目

今天没写完

晚上倒是有一段时间

不过我去弄Atom了......

明天计划:

切掉这个题 把以前做过的搜索题复习一下

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 	66, INF = 214748364;

int T, n, m, res = INF;
int a[N][N], flag;
char s[N];

int dx[3] = {0, 0, 1, -1};
int dy[3] = {1, -1, 0, 0};
int vs[N][N], vt[N][N];
int sdis[N][N], tdis[N][N];

struct node {int x, y;};

inline int bfs (int curx, int cury, int curs, int curt) {
    // if (x == nx && y == ny) calc();
    queue<node>qs; queue<node>qt;
  node l, r;
    l.x = curx, l.y = cury, r.x = curs, r.y = curt;
    qs.push(l); qt.push(r);
    memset (vs, 0, sizeof vs), memset (vt, 0, sizeof vt);
    memset (sdis, 0, sizeof sdis), memset (tdis, 0, sizeof tdis);
    int ans(0);
    while (qs.size()) {
        node tmp = qs.front(); qs.pop();
        for (int i = 0; i < 3; ++ i) {
            node nows;
            nows.x = tmp.x+dx[i], nows.y = tmp.y+dy[i];
            if ((nows.x > n)||(nows.x < 1)||(nows.y > m)||(nows.y < 1)) continue;
            if (!vs[nows.x][nows.y] && a[nows.x][nows.y]){
                vs[nows.x][nows.y] = 1;
                qs.push(nows);
                sdis[nows.x][nows.y] = sdis[tmp.x][tmp.y]+1;

            }
        }
    }
    while (qt.size()) {
        node tmp = qt.front(); qt.pop();
        for (int i = 0; i < 3; ++ i) {
            node nows;
            nows.x = tmp.x+dx[i], nows.y = tmp.y+dy[i];
            if ((nows.x > n)||(nows.x < 1)||(nows.y > m)||(nows.y < 1)) continue;
            if (!vt[nows.x][nows.y] && a[nows.x][nows.y]){
                vt[nows.x][nows.y] = 1;
                qt.push(nows);
                tdis[nows.x][nows.y] = tdis[tmp.x][tmp.y]+1;
            }
        }
    }
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j) {
            if ((!vs[i][j] || !vt[i][j]) && a[i][j]) {
                flag = true;
                return;
            }
        }
}

int main () {
    scanf ("%d", &T);
    while (T --> 0) {
        flag = false, res = 0;
        scanf ("%d%d", &n, &m);
        for (int i = 1; i <= n; ++ i) {
            scanf ("%s", s+1);
            for (int j = 1; j <= m; ++ j)
                a[i][j] = (s[j] == '#') ? 1 : 0;
        }
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= m; ++ j)
                if (a[i][j])
        for (int ni = 1; ni <= n; ++ ni)
            for (int nj = 1; nj <= m; ++ nj)
                if (a[ni][nj])
                    bfs (i, j, ni, nj);
        if (flag) cout << "-1" << '\n';
        else cout << res << '\n';
    }
    return 0;
}

Posted on Edited on In

题目

这里很容易想到广搜，设初始状态为\((i,j)\)，一共就只有六种变化

A杯倒满，B杯倒满，A杯倒出完，B杯倒出完，A到给B，B到给A

任意一种状态\(i\) 或者 \(j\)达到 \(C\) 就停止，注意要打印路径，我这里用一个string存的操作顺序。

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
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int N = 1e2+100;

int a, b, c;
int v[N][N];
bool flag = false;
string str[10] = {"", "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)","POUR(2,1)"};

struct node {
    int x, y, step; string s;
    node (int x, int y, int step, string s):x(x), y(y), step(step),s(s){}
};

inline void bfs () {
    queue<node>q;
    v[0][0] = 1;
    q.push(node(0, 0, 0, "0"));
    while(!q.empty()) {
        /* code */
        node tmp = q.front(); q.pop();
        if (tmp.x == c || tmp.y == c) {
            flag = 1;
            cout << tmp.step << '\n';
            for (int i = 1; i < tmp.s.length(); ++ i)
                cout << str[tmp.s[i]-'0'] << '\n';
            return;
        }
        if (tmp.x < a)
            if (!v[a][tmp.y])
                v[a][tmp.y] = 1, q.push(node(a, tmp.y, tmp.step+1, tmp.s+"1"));
        if (tmp.y < b)
            if (!v[tmp.x][b])
                v[tmp.x][b] = 1, q.push(node(tmp.x, b, tmp.step+1, tmp.s+"2"));
        if (tmp.x != 0)
            if (!v[0][tmp.y])
                v[0][tmp.y] = 1, q.push(node(0, tmp.y, tmp.step+1, tmp.s+"3"));
        if (tmp.y != 0)
            if (!v[tmp.x][0])
                v[tmp.x][0] = 1, q.push(node(tmp.x, 0, tmp.step+1, tmp.s+"4"));
        if (tmp.x != 0 && tmp.y < b) {
            int nx, ny;
            if (tmp.x <= b-tmp.y) nx = 0, ny = tmp.x+tmp.y;
            else nx = tmp.x+tmp.y-b, ny = b;
            if (!v[nx][ny]) 
                v[nx][ny] = 1, q.push(node(nx, ny, tmp.step+1, tmp.s+"5"));
        }
        if (tmp.y != 0 && tmp.x < a) {
            int nx, ny;
            if (tmp.y <= a-tmp.x) nx = tmp.x+tmp.y, ny = 0;
            else nx = a, ny = tmp.x+tmp.y-a;
            if (!v[nx][ny]) 
                v[nx][ny] = 1, q.push(node(nx, ny, tmp.step+1, tmp.s+"6"));
        }
    }
}

int main () {
    cin >> a >> b >> c;
    bfs ();
     if (!flag) puts ("impossible");	
    return 0;
}

分为六种情况讨论

反正现在的我一眼看上去，不知道正解

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
/*
 * By Youngore
 * Time:20.10.16
 * */
#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
const int N = 110;

int a, b, c, flg;
int v[N][N];
string str[10] = {"", "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};
struct yhy
{
	int x, y, stp;
	string s;
	yhy(int x, int y, int stp, string s):x(x), y(y), stp(stp), s(s){}
};

inline void bfs()
{
	queue<yhy>q; v[0][0] = 1;
	q.push(yhy(0, 0, 0, "0"));
	while (! q.empty())
	{
		yhy tmp = q.front(); q.pop();
		if (tmp.x == c || tmp.y == c)
		{
			flg = 1;
			cout << tmp.stp << '\n';
			for (int i = 1; i <= tmp.stp; ++ i) cout << str[tmp.s[i] - '0'] << '\n';
			break;
		}
		if (tmp.x != a && ! v[a][tmp.y])
		{
			v[a][tmp.y] = 1;
			q.push(yhy(a, tmp.y, tmp.stp + 1, tmp.s + "1"));
		}
		if (tmp.y != b && ! v[tmp.x][b])
		{
			v[tmp.x][b] = 1;
			q.push(yhy(tmp.x, b, tmp.stp + 1, tmp.s + "2"));
		}
		if (tmp.x && ! v[0][tmp.y])
		{
			v[0][tmp.y] = 1;
			q.push(yhy(0, tmp.y, tmp.stp + 1, tmp.s + "3"));
		}
		if (tmp.y && !v[tmp.x][0])
		{
			v[tmp.x][0] = 1;
			q.push(yhy(tmp.x, 0, tmp.stp + 1, tmp.s + "4"));
		}
		if (tmp.x && tmp.y != b)
		{
			int nx, ny;
			if (tmp.y + tmp.x <= b) nx = 0, ny = tmp.x + tmp.y;
			else nx = tmp.x + tmp.y - b, ny = b;
			if (! v[nx][ny]) q.push(yhy(nx, ny, tmp.stp + 1, tmp.s + "5"));
		}
		if (tmp.y && tmp.x != a)
		{
			int nx, ny;
			if (tmp.x + tmp.y <= a) nx = tmp.x + tmp.y, ny = 0;
			else nx = a, ny = tmp.x + tmp.y - a;
			if (! v[nx][ny]) q.push(yhy(nx, ny, tmp.stp + 1, tmp.s + "6"));
		}

	}
	if (! flg) puts("impossible");
	return;
}

inline int youngore()
{
	scanf ("%d%d%d", &a, &b, &c);
	bfs();
	return 0;
}

int search_ex = youngore();

signed main() {;};

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
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e4+66, INF = 250;

int T, res, len;
int a, b, i, dy;
char p[N], t[N], s[N], f[N];

int main () {
    scanf ("%d", &T);
    while (T --> 0) {
        ++ i; res = a = b = 0;
        cin >> len;
        scanf ("%s%s", p+1, t+1);
        scanf ("%s", s+1);
        while (1) {
            dy = a = b = 0;
            if (res == INF) {res = -1; break;}
            for (int i = 1; i <= (len<<1); ++ i) 
                f[i] = (i&1 == 1) ? t[++a] : p[++b];
            // cout << "-->";
            // for (int i = 1; i <= (len<<1); ++ i)
                // cout<<f[i];
            // cout << '\n';
            ++ res;
            for (int i = 1; i <= (len<<1); ++ i)
                if (f[i] == s[i])
                    ++ dy;
            if (dy == (len<<1)) break;
            for (int i = 1; i <= len; ++ i)
                p[i] = f[i], t[i] = f[len+i];
        }
        cout << i << ' ' << res << '\n';
    }
}

感觉做这个题真tm拉低我智商

这么水的数据

INF等于250 随便跑一跑就能水过“-1”

搜索个屁啊

就是个破模拟

不需要动一点脑子

花了我一个小时.....

草

垃圾题

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
// Prime Path 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 10000+10;
const int INF = 21474836;

int t, res, cnt;

int dp[N], v[N], prime[N];

inline int work (int num, int t, int c) {
    if (t == 0) return num/10*10+c;
    if (t == 1) return num/100*100+c*10+num%10;
    if (t == 2) return num/1000*1000+c*100+num%100;
    return c*1000+num%1000;
}

int main () {
    memset (v, 1, sizeof v);
    for (int i = 2; i <= N; ++ i) {
        if (v[i]) prime[++cnt] = i;
            for (int j = 1; j<=cnt && i*prime[j]<=N; ++ j) 
                v[i*prime[j]] = 0;
    }
    cin >> t;
    while (t --> 0) {
        int a, b;
        cin >> a >> b;
        if (a == b) {puts("0");continue;}
        memset (dp, INF, sizeof dp);
        dp[a] = 0;
        queue<int>q;
        q.push(a);
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            for (int i = 0; i < 4; ++ i)
                for (int j = 0; j < 10; ++ j) {
                    if (i == 3 && j == 0) continue;
                    int nxt = work (cur, i, j);
                    if (!v[nxt] || dp[nxt] <= dp[cur]) continue;
                    dp[nxt] = dp[cur]+1;
                    q.push(nxt);
                }
        }
        cout << dp[b] << '\n';
    }
}

PS:

1.easy \(bfs\)

2.but is not very easy to find a thought

3.I felt that I have thought vaguely but I can'nt make it.

I will still work hard!

两年后，再一次做这道题，思路清晰但是代码能力下降好多，debug了好长时间

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
/*
 * By Youngore
 * Time: 22.10.15
 * */
#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#define inf 10000
const int N = 1e4 + 66;
using namespace std;

int T, cnt, a[66];
int vis[N], pri[N], v[N];

inline void pre()
{
	memset(vis, 1, sizeof vis); vis[1] = 0;
	int i, j;
	for (i = 2; i <= inf; ++ i)
	{
		if (vis[i]) pri[++ cnt] = i;
		for (j = 1; j <= cnt && i * pri[j] <= inf; ++ j)
		{
			vis[i * pri[j]] = 0;
			if (! (i % pri[j])) break;
		}
	}
	return;
}

inline int youngore()
{
	scanf ("%d", &T); pre();
	while (T --> 0)
	{
		int x, y, i, j;
		scanf ("%d%d", &x, &y);
		memset(v, 0, sizeof v);
		queue<pair<int,int> >q; q.push(make_pair(x,0));
		v[x] = 1;
		while (! q.empty())
		{
			pair<int, int> nows = q.front(); q.pop();
			if (nows.first == y)
			{
				cout << nows.second << '\n';
				break;
			}
			int k = nows.first, cnt = 0;
			while (k)
			{
				a[++ cnt] = k % 10;
				k /= 10;
			}
			for (k = cnt; k >= 1; -- k)//枚举每一位
			{
				for (i = ((k == cnt) ? 1 : 0); i <= 9; ++ i)//枚举该位可以替换成那些数字
				{
					if (i == a[k]) //如果碰到了原位上的数字
						continue;
					int res = 0;
					for (j = cnt; j >= 1; -- j)//把每一位加和
						res = res * 10 + ((j == k) ? i : a[j]);
					if (vis[res] && !v[res]) q.push(make_pair(res, nows.second + 1)), v[res] = 1;
				}
			}
		}
	}
	return 0;
}

int search_ex = youngore();

signed main() {;}
/*
1
1033 8179
*/


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
#include <cstdio>
#include <iostream>
#define ull unsigned long long int 
using namespace std;

int n, k;

inline void dfs (ull ans, int n, int weishu) {
    if (k == 0) return;
    if (weishu == 20) return;
    if (ans%n == 0) {
        cout << ans << '\n';
        k = 0;
        return;
    }
    dfs (ans*10, n, weishu+1);
    dfs (ans*10+1, n, weishu+1);
}

int main () {
    while (scanf ("%d", &n)&& n != 0) {
        k = 1;
        dfs (1, n, 1);
    }
    return 0;
}

this is a easy topic

but I can not make it unless I can read the answer

To tell the truth, I was very terrible

Although the topic is easy but I don't know how to solve it

I will also try my best to welcome the NOIP2020.

PS:

1.we need the 'weishu == 20'

because the ull can held '19' so we much let the ull can search all

两年后再写

尝试用bfs写了一下，mle了

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
/*
 * By Youngore
 * Time: 22.10.15
 * */
#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#define ull unsigned long long
using namespace std;

int n;

inline int youngore()
{
	while (scanf ("%d", &n))
	{
		if (n == 0) return 0;
		queue<pair<ull, int> >q; q.push(make_pair(1, 1));
		while (q.size())
		{
			pair<ull, int> nows = q.front(); q.pop();
			if (nows.second == 20) continue;
			if (! (nows.first % n)) 
			{
				cout << nows.first << '\n';
				break;
			}
			q.push(make_pair(nows.first * 10, nows.second + 1));
			q.push(make_pair(nows.first * 10 + 1, nows.second + 1));
		}
	}
	return 0;
}

int search_ex = youngore();

signed main() {;}
/*
2
6
19
0
*/


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
73
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int N = 66, INF = 2147483647;

int n, m, res = INF;
int f[N];
int a[N][N], b[N][N], c[N][N], d[N][N];

inline void work (int x, int y) {
    c[x][y] = 1-c[x][y];
    c[x+1][y] = 1-c[x+1][y];
    c[x-1][y] = 1-c[x-1][y];
    c[x][y+1] = 1-c[x][y+1];
    c[x][y-1] = 1-c[x][y-1];
}

inline void check() {
    memset (b, 0, sizeof b);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            c[i][j] = a[i][j];
    for (int i = 1; i <= m; ++ i)
        if (f[i]) 
            work (1, i), b[1][i] = 1;
    for (int i = 2; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            if (c[i-1][j])
                work (i, j), b[i][j] = 1;
    for (int i = 1; i <= m; ++ i)
        if (c[n][i])
            return;
    int nows(0);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            if (b[i][j])
                ++ nows;
    if (nows < res){
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= m; ++ j)
                d[i][j] = b[i][j];
        res = nows;
    }
}

inline void dfs (int x) {
    if (x == m+1) {
        check();
        return;
    }
    f[x] = 0, dfs(x+1);
    f[x] = 1, dfs(x+1);
    return;
}

int main () {
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            scanf ("%d", &a[i][j]);
    dfs (1);
    if (res == INF) puts ("IMPOSSIBLE");
    else {
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= m; ++ j)
                cout << d[i][j] << ' ';
            cout << '\n';
        }
    }
    return 0;
}

ps:

今天比较心累 就不想用英文了

因为拼单词还得动脑子

这个题先捋一遍思想吧:

我们枚举第一行的状态，通过第一行来决定以下的一些行数。

thus更新答案

但是这题特别tmd狗

"如果最小解有多个，则输出在字典序意义下最小的那个"

真恶心

先埋下一个坑

因为我还没有搞透彻

"先搜0，再搜1能保证字典序最优"

"check函数是s<ans而不是s<=ans"

"因为先搜到的答案一定字典序比后搜到的字符串优"

"#define 字符串 方案"

" 那么后搜到的方案如何干掉先搜到的方案呢——唯有移动步数比先搜到的少"

\(7.14update\):

Q:为什么从零开始搜，要比从1开始搜 更正确？

A:因为字典序是 0 < 1 并且是 '01111' < '10000'还要比较最高位

所以我们从零开始搜的话，我们只可能是如下的搜索过程:‘00001’-->'00011' --> '00111' --> '.....'默认保证了字典序是从小往大搜的

而后面的方案数 如果想干掉之前的ans就必须满足 移动的步数比ans小（即为总的1的个数没有当前ans的1的个数多）

我们不需要再考虑字典序的问题，因为我们先从0开始搜，默认保证了我们字典序几就是从小到大这样排列的

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
// catch that cow
#include <iostream>
using namespace std;

const int N = 1e7+10;

int n, k, x;
int q[N], v[N], dis[N];

int main () {
    cin >> n >> k;
    if (n > k) {cout << n-k; return 0;}
    int s = 0, t = 1;
    q[1] = n, v[n] = 1;
    while (s <= t) {
        ++ s;
        for (int i = 1; i <= 3; ++ i) {
            int x = q[s];
            if (i == 1) ++ x; 
            if (i == 2) -- x;
            if (i == 3) x<<=1;
            if (x >= 0 && x <= 100000) 
                if (!v[x]) {
                    v[x] = 1;
                    q[++ t] = x;
                    dis[x] = dis[q[s]] + 1;
                }
        }
    }
    cout << dis[k];
    return 0;
}

PS:

1.before today I break for two days;

2.It is a very easy bfs.

The only season why I cann't solve this problem is I was very sily

第二次做，考虑一下正确性

1
s.cnt = now.cnt + 1;
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int n, k;
int vis[100066];
struct yhy{int w, cnt;};
queue<yhy>q;

inline int youngore()
{
	scanf ("%d%d", &n, &k);
	yhy now; now.w = n, now.cnt = 0;
	q.push(now);
	while (q.size())
	{
		now = q.front(); q.pop();
		if (now.w == k)
		{
			cout << now.cnt;
			return 0;
		}
		yhy s;
		for (int i = 1; i <= 3; ++ i)
		{
			if (i == 1) s.w = now.w + 1;
			if (i == 2) s.w = now.w - 1;
			if (i == 3) s.w = now.w * 2;
			if (s.w < 0 || s.w > 100000)
			{
				continue;
			}
			if (! vis[s.w])
			{
				vis[s.w] = 1;
				s.cnt = now.cnt + 1;
				q.push(s);
			}
		}
		//cout << "!!!----> " << q.size() << '\n';
	}
	return 0;
}

signed main(){youngore();}
/*
*/

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
*/
0%