记录一下做过的题目

穿越雷区

这是一道基础的 BFS 题目

题目描述

X 星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。

某坦克需要从 A 区到 B 区去（A, B 区本身是安全区，没有正能量或负能量特征），
怎样走才能路径最短?
已知的地图是一个方阵，上面用字母标出了 A, B 区，其他区都标了正号或负号分别
表示正、负能量辐射区。
例如：
A + − + −
− + − − +
− + + + −
− + − + +
B + − + −
坦克车只能水平或垂直方向上移动到相邻的区。

难点分析

一开始不知道怎么处理AB两个点的初始化，其实只要初始化成 -1 就可以了，这样后续就不会因为 与 设置的 0 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;

int p[105][105];
int vis[105][105];
int n;
int xa,ya,xb,yb;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

queue<pair<int,int>> q;

bool check(int x,int y){
    if(x<1||y<1||x>n||y>n || vis[x][y] != 0){
        return false;
    }
    return true;
}

int bfs(){
    q.push({xa,ya});
    while (q.size())
    {
        int x = q.front().first,y = q.front().second;
        q.pop();
        // 判断退出条件
        
        for(int i = 0 ; i<4 ; i++){
            int xx = x+dx[i],yy = y+dy[i];
            // 判断退出
            if(xx==xb&&yy == yb){
            return vis[x][y]+1;
        }
        if(!check(xx,yy) || p[xx][yy] == p[x][y]){
            continue;
        }
            vis[xx][yy] = vis[x][y] + 1;
            q.push({xx,yy});
            
        }
    }
    
}

int main(){
    string s;
    
    cin >> n;
    for(int i = 1 ; i<=n ;i++){
        cin >> s;
        for(int k = 0 ; k<n ; k++){
            if(s[k] == '+')
            p[i][k+1] = 1;
            else if(s[k] =='-'){
                p[i][k+1] = 0;
            }else if(s[k] == 'A'){
                xa = i;
                ya = k+1;
                p[xa][ya] = -1;
            }else{
                xb = i;
                yb = k+1;
                p[xb][yb] = -1;
            }
        }
    }
    cout << bfs();
    system("pause");
    return 0;
}

这题也可以采用 dfs 来做，不过要学会减枝

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
#include<bits/stdc++.h>
using namespace std;

const int N = 1e2 + 10;
int n,ans; // ans 记录答案
int a[N][N];
int vis[N][N];
int dx[] = {0,0,1,-1};
int dy[] = {1,1,0,0};
pair<int,int> st,ed;

void dfs(int x,int y,int cnt){
    if(cnt>ans) return;
    if(cnt>vis[x][y]) return;
    if(x<1 || x>n || y<1 || y>n) return;
    if(x==ed.first && y==ed.second){
        ans = cnt;
        return ;
    }
    vis[x][y] = cnt;
    for(int i = 0; i<4 ;i++){
        int xx = x+dx[i],yy = y+dy[i];
        if(a[xx][yy]!=a[x][y]) dfs(xx,yy,cnt+1);
    }
}

int main(){
    cin >> n;
    ans = 0x3f3f3f3f;
    for(int i = 1 ; i<=n ;i++) for(int j = 1 ; j<=n ;j++)  vis[i][j] = 0x3f3f3f3f;
    for(int i = 1 ; i<=n ;i++){
        for(int j = 1 ; j<= n ;j++){
            char x;
            cin >> x;
            if(x == 'A') st.first = i, st.second = j,a[i][j] = -1;
            else if(x == 'B') ed.first = i , ed.second = j ,a[i][j] = -1;
            else if(x == '+') a[i][j] = 1;
            else a[i][j] = 0;
        }
    }
    dfs(st.first,st.second,0);
    cout << ans <<'\n';
    return 0;
}

01迷宫

有一个仅由数字 $0$ 与 $1$ 组成的 $n \times n$ 格迷宫。若你位于一格 $0$ 上，那么你可以移动到相邻 $4$ 格中的某一格 $1$ 上，同样若你位于一格 $1$ 上，那么你可以移动到相邻 $4$ 格中的某一格 $0$ 上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入格式

第一行为两个正整数 $n,m$。

下面 $n$ 行，每行 $n$ 个字符，字符只可能是 $0$ 或者 $1$，字符之间没有空格。

接下来 $m$ 行，每行两个用空格分隔的正整数 $i,j$，对应了迷宫中第 $i$ 行第 $j$ 列的一个格子，询问从这一格开始能移动到多少格。

输出格式

$m$ 行，对于每个询问输出相应答案。

样例 #1

样例输入 #1

1
2
3
4
5
2 2
01
10
1 1
2 2

样例输出 #1

1
2
4
4

提示

对于样例，所有格子互相可达。

  • 对于 $20\%$ 的数据，$n \leq 10$；
  • 对于 $40\%$ 的数据，$n \leq 50$；
  • 对于 $50\%$ 的数据，$m \leq 5$；
  • 对于 $60\%$ 的数据，$n,m \leq 100$；
  • 对于 $100\%$ 的数据，$1\le n \leq 1000$，$1\le m \leq 100000$。

这一题我在做的时候一开始遇到了输入问题，后面改进以后遇到了超时问题

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
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m;
int p[N][N];
int vis[N][N];

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

int ans = 1; // 记录答案

void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 1 || xx > n || yy <1 || yy> n || vis[xx][yy] != 0 || p[xx][yy] == p[x][y]) continue;
        vis[xx][yy] = 1;
        ans++;
        dfs(xx, yy);
    }
}

int main() {
    cin >> n >> m;
    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 1; j <= n; j++) {
            char a = s[j - 1];
            if (a == '0') { p[i][j] = 0; }
            else if (a == '1') p[i][j] = 1;
            else p[i][j] = 9;
        }
    }
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        memset(vis, 0, sizeof vis), ans = 1, vis[x][y] = 1;
        dfs(x, y);
        cout << ans << endl;
    }
    system("pause");
    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
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+5;

int f[N], h[N],n; // f表示父节点，h表示连通的块数
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
char s[1005][1005];

// 查
int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}
// 合并
void unionn(int x, int y) {

	if (find(x) != find(y)) {
		h[find(x)] += h[find(y)], f[find(y)] = f[find(x)];
	}
}

void unionn(int x, int y)//并
{
	int r1 = find(x), r2 = find(y);
	if (find(x) != find(y))h[find(x)] += h[find(y)], f[find(y)] = f[find(x)];
}

int dfs(int x, int y) {
	if (f[x * n + y] != -1) return find(x * n + y);
	f[x * n + y] = x * n + y, h[x * n + y] = 1;// 构造映射,且初始化
	for (int i = 0; i < 4; i++) {
		int xx = x + dx[i], yy = y + dy[i];
		if (xx >= 0 && xx < n && yy >= 0 && yy < n && s[xx][yy] != s[x][y]) unionn(x * n + y, dfs(xx, yy));
	}
	return find(x * n + y);
}

int main() {
	int t;
	cin >> n >> t;
	memset(f, -1, sizeof (4*n*n));
	for (int i = 0; i < n; i++) {
		scanf("%s", s[i]);
	}
	int i, j;
	while (t--)
	{
		scanf("%d%d", &i, &j);
		cout << h[dfs(i - 1, j - 1)] << endl;
	}
	return 0;
}

落谷 1168

image-20240309115302683

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
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int>, less<int>> da;
priority_queue<int, vector<int>, greater<int>> xiao;

int m,a;

int main() {
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a;
		if (i == 1) {
			xiao.push(a);
			cout << xiao.top() << endl;
		}
		else {
			if (i % 2 ==0) {  
				int c = xiao.top();
				if (a <= c) {
					da.push(a);
				}
				else {
					xiao.pop(); xiao.push(a); da.push(c);
				}
			}
			else {
				int c = da.top();
				if (a >= c) {
					xiao.push(a);
				}
				else {
					da.pop(); da.push(a); xiao.push(c);
				}
				cout << xiao.top() << endl;
			}
		}
	}
}