寒假训练——第二周（BFS）

A - Multiply and Rotate

A - Multiply and Rotate

思路：

• 分两种情况 $BFS$

注意：

• 看清楚范围再确定此情况是否成立

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

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

int n, m;
int a;
int cnt[N];
int q[N];
bool st[N];

int bfs()
{
    int hh = 0, tt = -1;
    q[ ++ tt] = 1;
    cnt[1] = 0;
    
    while(hh <= tt)
    {
        int t = q[hh ++ ];
        
        if(t == n) return cnt[t];
        
        if(st[t]) continue;
        st[t] = true;
        
        if(t * a <= N)
        {
            int b = t * a;
            q[ ++ tt] = b;
            cnt[b] = cnt[t] + 1;
        }
        
        if(t >= 10 && t % 10 != 0)
        {
            int b = t % 10 * pow(10, (int)log10(t)) + t / 10;
            q[ ++ tt] = b;
            cnt[b] = cnt[t] + 1;
        }
    }
    
    return -1;
}


void solve()
{
    cin >> a >> n;
    
    cout << bfs() << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    while(T -- )
        solve();
    
    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

---

B - 移动玩具

B - 移动玩具

思路：

• 二进制表示 + 位运算交换 + $BFS$

核心代码五行：[HAOI2008]移动玩具（五行核心代码）

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

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

int n, m;
int start, ed;
string str[10];
int dist[N];
bool st[N];
queue<int> q;

// 调试代码，
// 作用：输出矩阵
// void print(int x)
// {
//     for (int i = 0, t = 15; i < 4; i ++ )
//     {
//         for (int j = 0; j < 4; j ++, t -- )
//             cout << ( (x >> t) & 1) << " ";
//         cout << endl;
//     }
    
//     cout << endl;
// }

// 交换 last 与 now 位上的数字
void change(int t, int last, int now)
{
    if( ((t >> last) & 1) == ((t >> now) & 1)) 
        return;
    
    int tt = t ^ (1 << last) ^ (1 << now);
    
    dist[tt] = dist[t] + 1;
    q.push(tt);
}

// 宽搜框架
int bfs()
{
    memset(dist, 0x3f, sizeof dist);
    
    q.push(start);
    dist[start] = 0;
    
    int cnt = 0;
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        if(t == ed) return dist[ed];
        
        if(st[t]) continue;
        st[t] = true;
        
        // 直接搜即可（总状态位 2^16 = 65536 种，
        // bfs 为线性时间复杂度，直接搜 时间很充足
        for (int i = 15; i >= 0 ; i -- )
        {
            // if( ((t >> i) & 1) ^ ((start >> i) & 1))
            // 本想简化一下代码，，但此行代码不可加上
            // 加上会 WA 一个数据
            // 数据如下：
            // 0011
            // 1100
            // 0011
            // 1100
            
            // 1111
            // 1001
            // 1001
            // 0000
            // 若加上则左上角的11永远出不去，无法到外面导致返回无解 -1
            // 因此最终代码代码为：
            
            // if( ((t >> i) & 1) ^ ((start >> i) & 1))
            //{
                if(i % 4 > 0 ) change(t, i, i - 1); // 和左边交换
                if(i % 4 < 3 ) change(t, i, i + 1); // 和右边交换
                if(i / 4 > 0 ) change(t, i, i - 4); // 和上边交换
                if(i / 4 < 3 ) change(t, i, i + 4); // 和下边交换
            //}
            
            
        }
        cnt ++;
    }
    
    return -1;
}

void solve()
{
    for (int i = 0; i < 4; i ++ )
        cin >> str[i];
    
    // 状压 ed
    for (int i = 0, t = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ , t ++ )
            ed = (ed << 1) + (str[i][j] - '0');
    
    for (int i = 0; i < 4; i ++ )
        cin >> str[i];
    
    // 状压 start
    for (int i = 0, t = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ , t ++ )
            start = (start << 1) + (str[i][j] - '0');
    
    cout << bfs() << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    while(T -- )
        solve();
    
    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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

---

C - 最长距离

C - 最长距离

思路：

• 只有01，考虑双端队列广搜

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 50, M = 10010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

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

int n, m, num;
string str[N];
int dist[N][N];
bool st[N][N];
double ans = -1e9;


double cal(double x1, double y1, double x2, double y2) 
{
    double res = sqrt(fabs(x1 - x2) * fabs(x1 - x2) + fabs(y1 - y2) * fabs(y1 - y2));
    return res;
}

void bfs(int x, int y)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    
    dist[x][y] = 0;
    
    deque<PII> q;
    q.push_back({x, y});
    
    while(q.size())
    {
        auto t = q.front();
        q.pop_front();
        
        int x = t.x, y = t.y;
        
        if(st[x][y]) continue;
        st[x][y] = true;
        
        for(int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            
            int w = str[a][b] - '0';
            int d = dist[x][y] + w;
            
            if(d <= dist[a][b])
            {
                dist[a][b] = d;
                if(w) q.push_back({a, b});
                else q.push_front({a, b});
            }
        }
    }

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if(dist[i][j] <= num)
                ans = max(ans, cal(x, y, i, j));
}

void solve()
{
    cin >> n >> m >> num;
    
    for (int i = 0; i < n; i ++ )
            cin >> str[i];
    
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if(str[i][j] == '0') bfs(i, j);
    
    printf("%.6lf\n", ans);
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    while(T -- );
        solve();
    
    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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

---

D - 8 Puzzle on Graph

D - 8 Puzzle on Graph

思路：

• 八数码变形题，参考八数码代码即可

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1010, M = 1010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

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

int n, m, num;
map<string, int> dist;
map<string, bool> st;

int h[N], e[M], ne[M], idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs(string state)
{
    dist[state] = 0;
    
    queue<string> q;
    q.push(state);
    
    string ed = "x123456780";
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        
        if(t == ed) return dist[t];
        
        //cout << t << endl;
        
        int x = t.find("0");
        for (int i = h[x]; ~i; i = ne[i])
        {
            int j = e[i];
            
            string ss = t;
            swap(ss[x], ss[j]);
            
            if(dist.count(ss)) continue;
            
            dist[ss] = dist[t] + 1;
            q.push(ss);
        }
    }
    
    return -1;
}

void solve()
{
    cin >> n;
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    int x;
    string state = "x000000000";
    for (int i = 1; i <= 8; i ++ )
    {
        cin >> x;
        state[x] = i + '0';
    }
    
    cout << bfs(state) << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    while(T -- )
        solve();
    
    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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

---

E - Labyrinth

E - Labyrinth

思路：

• 每个点记录 向右向左走的此数即可
• 注意的是，优先走上下格子，用 $deque$ 插入队头正合适

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2010, M = 1010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

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

int n, m;
int sx, sy;
int l, r;

int st[N][N];
char g[N][N];
PII dist[N][N];

int bfs()
{
    int res = 1;
    
    deque<PII> q;
    st[sx][sy] = true;
    dist[sx][sy] = {0, 0};
    q.push_back({sx, sy});
    
    while(q.size())
    {
        auto t = q.front();
        q.pop_front();
        
        int xx = t.x, yy = t.y;
        
        for (int i = 0; i < 4; i ++ )
        {
            bool f = 0;
            int a = xx + dx[i], b = yy + dy[i];
            
            if(a < 1 || a > n || b < 1 || b > m) continue;
            if(g[a][b] == '*') continue;
            if(st[a][b]) continue;
            
            if(i == 1)
            {
                if(dist[xx][yy].y >= r) continue;
                else dist[a][b] = {dist[xx][yy].x, dist[xx][yy].y + 1};
                f = 1;
            }

            if(i == 3)
            {
                if(dist[xx][yy].x >= l) continue;
                else dist[a][b] = {dist[xx][yy].x + 1, dist[xx][yy].y};
                f = 1;
            }
            
            if(!f) dist[a][b] = dist[xx][yy];
            
            res ++;
            
            st[a][b] = true;
            
            //cout << i << "|||" << xx << " " << yy <<  "|||" << a << " " << b << endl;
            //cout << " " << "|||" << dist[xx][yy].x << " " << dist[xx][yy].y << "|||" << dist[a][b].x << " " << dist[a][b].y << endl;
            
            if(i & 1) q.push_back({a, b});
            else q.push_front({a, b});
        }
    }
    
    return res;
}

void solve()
{
    cin >> n >> m;
    cin >> sx >> sy;
    cin >> l >> r;
    
    for (int i = 1; i <= n; i ++ )
        cin >> g[i] + 1;
    
    //cout << dist[3][1].x << " " << dist[3][1].y << endl;
    
    cout << bfs() << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    while(T -- )
        solve();
    
    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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110