#include <stdio.h>
#include <string.h>
#include <math.h>
#include "io.h"
#define MAXN 20

char map[MAXN][MAXN], vis[MAXN][MAXN][MAXN * MAXN][4];
int k;
int ex, ey;
int n, m;
int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

int in(int x, int y)
{
    return (x >= 0 && x < n && y >= 0 && y < m);
}
char visnake[10];
int ans = MAXN * MAXN * 10;
int sx, sy;
// walk
int tmp = 0;
void walk(char tmpmap[MAXN][MAXN], int x, int y, int tox, int toy)
{
    if (tmpmap[tox][toy] == '0' + k)
    {
        tmp = tmpmap[tox][toy] - '0';
    }
    tmpmap[tox][toy] = tmpmap[x][y];
    if (tmpmap[x][y] == '0' + k)
    {
        tmpmap[x][y] = '.';
    }
    if ((tmp) && (tmpmap[tox][toy] == tmp - 1 + '0'))
    {
        tmpmap[x][y] = tmp + '0';
    }
    int nx = x, ny = y;
    for (int i = 0; i < 4; i++)
    {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (tmpmap[tx][ty] == tmpmap[x][y] + 1)
        {
            visnake[tmpmap[tx][ty] - '0'] = 1;
            nx = tx, ny = ty;
            break;
        }
    }
    if (nx == x && ny == y)
    {
        return;
    }
    walk(tmpmap, nx, ny, x, y);
}
// update
void update(char tmpmap[MAXN][MAXN], int sx, int sy, int tx, int ty)
{
    tmp = 0;
    memset(visnake, 0, sizeof(visnake));
    walk(tmpmap, sx, sy, tx, ty);
    //disp(tmpmap, n, m); // 每update一次就输出
}

struct node
{
    char map[MAXN][MAXN];
    int x, y;
    int step;
    int dir;
} q[MAXN * MAXN * 10];

struct node make_node(const char map[MAXN][MAXN], int x, int y, int step, int dir)
{
    struct node tmp;
    memcpy(tmp.map, map, MAXN * MAXN);
    tmp.x = x, tmp.y = y;
    tmp.step = step;
    tmp.dir = dir;
    return tmp;
}

int bfs()
{
    int l = 0, r = 0;
    for (int i = 0; i < 4; i++)
    {
        char tmp[MAXN][MAXN];
        memcpy(tmp, map, MAXN * MAXN);
        int tx = sx + dir[i][0];
        int ty = sy + dir[i][1];
        if (in(tx, ty) && !vis[tx][ty][1][i] && ((tmp[tx][ty] == '0' + k&&k!=2) || tmp[tx][ty] == '@' || tmp[tx][ty] == '.'))
        {
            vis[tx][ty][1][i] = 1;
            update(tmp, sx, sy, tx, ty);
            q[r++] = make_node(tmp, tx, ty, 1, i);
        }
    }
    while (l < r)
    {
        struct node tmp = q[l++];
        char tmpmap[MAXN][MAXN];
        memcpy(tmpmap, tmp.map, MAXN * MAXN);
        for (int i = 0; i < 4; i++)
        {
            memcpy(tmpmap, tmp.map, MAXN * MAXN);
            int tx = tmp.x + dir[i][0], ty = tmp.y + dir[i][1];
            if (in(tx, ty) && !vis[tx][ty][tmp.step + 1][i] && (((tmpmap[tx][ty] == '0' + k&&k!=2)) || (tmpmap[tx][ty] == '@') || (tmpmap[tx][ty] == '.')))
            {
                if(tmpmap[tx][ty]=='@')
                {
                    return tmp.step+1;
                }
                vis[tx][ty][tmp.step + 1][i] = 1;
                update(tmpmap, tmp.x, tmp.y, tx, ty);
                q[r++] = make_node(tmpmap, tx, ty, tmp.step + 1, i);
            }
        }
    }
    return -1;
}

void user_control()
{
    //disp(map, n, m);
    int ch;

    while (scanf("%d", &ch))
    {
        switch (ch)
        {
        case 2:
            // down
            update(map, sx, sy, sx + 1, sy);
            sx++;
            break;
        case 4:
            // left
            update(map, sx, sy, sx, sy - 1);
            sy--;
            break;
        case 8:
            // up
            update(map, sx, sy, sx - 1, sy);
            sx--;
            break;
        case 6:
            // right
            update(map, sx, sy, sx, sy + 1);
            sy++;
            break;
        default:
            break;
        }
    }
}
#define RUN
int main()
{
    // freopen("out.txt", "w+", stdout);

    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", map[i]);
    }

    disp(map, n, m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] >= '1' && map[i][j] <= '9')
            {
                if (map[i][j] - '0' > k)
                {
                    k = map[i][j] - '0';
                }
            }
            if (map[i][j] == '1')
            {
                sx = i, sy = j;
            }
            if (map[i][j] == '@')
            {
                ex = i, ey = j;
            }
        }
    }
#ifdef RUN
    printf("%d", bfs());
#endif
#ifdef DEBUG
    user_control();
#endif
}

正方形 - 计蒜客

题意分析：

搜索4条边，使得4条边满足相等而且等于sum/4，即数组所有元素一起能构成一个正方形

初代算法：

dfs(int id, int l1,int l2,int l3,int l4)
{
    dfs(id+1,l1+p[id],l2,l3,l4);
    dfs(id+1,l1,l2+p[id],l3,l4);
    dfs(id+1,l1,l2,l3+p[id],l4);
    dfs(id+1,l1,l2,l3,l4+p[id]);
}

对4条边进行搜索 会超时

分析：

每条边都是等效的，因此重复状态很多

不是很理解ac代码的k的作用.

#include <stdio.h>
#define MAXN 25
long long p[MAXN], n;
long long sum = 0;
long long a = 0;

int ok = 0;
long long vis[MAXN];
// x表示当前正在搜索第x(0,1,2)条边
// sum 表示当前搜索的边的长度
// k表示//避免重复状况（？）
// 即 若当前dfs的k仍从1开始，
// 遇到一个下标介于1和k之间的下标（记为j），
// 并且发现vis[j]=0，
// 那么其实已经说明j被这层dfs前面的dfs搜索过，
// 而且还不是正确答案状态，
// 可以省略这些状态，
// 所以每层k都要进行+1
void dfs(int sum,int k,int x)
{
    if(ok)
    {
        return;
    }
    if(x==3)
    {
        ok=1;
        return;
    }
    if(sum>a)
    {
        return;
    }
    if(sum==a)
    {
        dfs(0,0,x+1);
    }
    for(int i =k;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            dfs(sum+p[i],i+1,x);
            vis[i]=0;
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &p[i]);
        sum += p[i];
    }
    if(sum%4!=0)
    {
        printf("No");
        return 0; 
    }
    a = sum / 4;

    for(int i = 1;i<=n;i++)
    {
        if(p[i]>a)
        {
            printf("No");
            return 0;
        }
    }
    dfs(0,1,0);
    if (ok)
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
}

引爆炸弹 - 来自计蒜客小学期

题目：

题意分析：

1.引爆一个炸弹，则属于该行该列的炸弹都会被引爆，结果被引爆的每个炸弹也递归引爆剩余的炸弹

2.最少需要手动引爆多少个，我们可以把会连续引爆的炸弹们归为同一个集合里面，这个集合里的任何一个炸弹被引爆，整个集合都会被引爆。因此这个集合的所有炸弹是等效的

3.那么我们只需要首先引爆某个炸弹，然后对集合进行标记引爆，搜索染色直到所有炸弹都炸了。

思路：

1. 统计地图中的所有炸弹和炸弹坐标

2. 先引爆某个炸弹

3. 对这个炸弹所在的集合进行染色

4. 深搜，即枚举剩下的炸弹，找到剩下的集合 如果找到了 则手动的步数+1

注意：

1. 只需要进行染色即可 不需要recolor

2. dfs起点只需要随意一个炸弹即可

3. 地图没有存储的必要

代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 666
char map[MAXN][MAXN];
int n, m;
int ans = MAXN * MAXN;
struct BOMB
{
    int x, y;
} bombs[MAXN * MAXN];
struct VISB
{
    char visb;
    int father;
} visb[MAXN * MAXN];
int bombcnt;
int exploded;
int queue[MAXN*MAXN],tot;
inline int same_block(int i, int j)
{
    if ((bombs[i].x == bombs[j].x) || (bombs[i].y == bombs[j].y))
    {
        return 1;
    }
    return 0;
}
void color_dfs(int b)
{
    queue[++tot] = b;
    while(tot!=0)
    {
        int x = queue[tot--];
        for(int i = 0;i<bombcnt;i++)
        {
            if(same_block(x,i)&&!visb[i].visb)
            {
                exploded++;
                if(exploded==bombcnt)
                {
                    return;
                }
                visb[i].visb = 1;
                visb[i].father = x;
                queue[++tot] = i;
            }
        }
    }
}
void decolor_dfs(int b)
{
    queue[++tot] = b;
    while(tot!=0)
    {
        int x = queue[tot--];
        for(int i =0;i<bombcnt;i++)
        {
            if(same_block(x,i)&&visb[i].visb&&visb[i].father==x)
            {
                visb[i].visb = 0;
                exploded--;
                visb[i].father = -1;
                queue[++tot] = i;
            }
        }
    }
}

int dfs(int b, int cnt)
{
    if (cnt > ans)
    {
        return 0;
    }
    color_dfs(b);
    if (exploded == bombcnt)
    {
        printf("%d",cnt);
        return 1;
    }
    for (int i = 0; i < bombcnt; i++)
    {
        if (!visb[i].visb)
        {
            if(dfs(i, cnt + 1))
            {
                return 1;
            }
        }
    }
    //decolor_dfs(b);
    return 0;
}
int main()
{
    freopen("E:\\Downloads\\4.txt","r",stdin);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", map[i]);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] == '1')
            {
                bombs[bombcnt].x = i;
                bombs[bombcnt].y = j;
                bombcnt++;
            }
        }
    }

    dfs(rand()%bombcnt, 1);

}

保龄了 B不会dp C不知道是不是贪心，也不会搜索

【管理员】ロリータ 20:22:43 https://www.acwing.com/problem/content/5731/

【管理员】ロリータ 20:22:52 https://www.acwing.com/problem/content/5732/

第一周周报

提交时间

2024/07/06

本周解决的问题

C语言复习

debug练习

git的简单使用

bash的简单命令

简单数据结构和算法

测试方法

开发模式

遇到的困难

想不出算法来

解决方法：多看题解，参考题解。

收获

1.满足了我对普及组信息学竞赛集训时光的幻想

1.巩固C语言基础

2.了解了gdb调试方法

3.对项目开发流程具有了了解

经验

太菜了没啥分享的

1.尽快完成进度，不要投机取巧

2.一道题不建议想太久，到一定程度即可放弃

对本周课程安排 意见 | 建议

1.建议改良麦克风，其他教室真的听不太清，时而清楚时而不清楚

对助教管理方式&教学方式 意见 | 建议

1.讲题提供思路即可，对着代码感觉反而不清晰

其他

暂无