头像

Loopback127


访客:2111

离线:28天前



#include<bits/stdc++.h>
using namespace std;
const int N=100;
typedef pair<int,int> PII;
int g[N][N];
int d[N][N];
int n,m;

int bfs(){
    queue<PII> p;
    p.push({0,0});
    d[0][0]=0;

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

    while(p.size()){
        auto h=p.front();
        p.pop();
        for(int i=0;i<4;i++){
           int x=h.first+dx[i];
            int y=h.second+dy[i]; 

        if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1){
            d[x][y]=d[h.first][h.second]+1;
            p.push({x,y});
        }

     }

    }



    return d[n-1][m-1];
}



int main(){
    memset(d,-1,sizeof d);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&g[i][j]);
        }
    }
    cout<<bfs()<<endl;
}



Loopback127
3个月前
//二叉树,如果题目里给的是边那么往往是图的问题
struct node{
    int data;
    node* lchild;
    node* rchild;
}
node* root = NULL;   //二叉树建树前根节点不存在

node* newNode(int v){
    node* Node = new node;
    Node->data = v;
    Node->lchild = Node->rchild =NULL;
    return Node;
}

void search(node* root,int x,int newdata)  //二叉树节点的查找、修改
{
    if(root == NULL){
        return;
    }
    if(root->data == x){
        root ->data = newdata;
    }
    search(root->lchild,x,newdata);
    search(root->rchild,x,newdata);
}

void insert(node* &root,int x)    //关键一点是根节点指针root用了引用&,在函数
{                                 //里修改root会直接修改原变量,insert()必须加引用
    if(root == NULL){
        root = newNode(x);
        return;
    }
    if(由二叉树的性质,x插在左子树){
        insert(root->lchild,x);
    }
    else{
        insert(root->rchild,x);
    }
}

node* Create(int data[],int n)
{
    node* root = NULL;
    for(int i=0;i<n;i++)
        insert(root,data[i]);
    return root;
}


void preorder(node* root){
    if(root == NULL)
        return;                   //到达空树,递归边界
    printf("%d\n",root->data);    //举例,比如输出这个点的值,可以为char等等任意类型
    preorder(root->lchild);
    preorder(root->rchild);
}

//树的遍历
struct node{
    int data;
    int child[N];    //指针域,用于存放所有子节点的下标
}Node[N];


int idx;
int newNode(int v)
{
    Node[idx].data = v;
    Node[idx].child.clear();     //清空子结点
    return idx++;                //返回结点下标,并令idx自增
}

//在考试中涉及非二叉树的树的考察是,
//一般都给出结点的编号,并且编号是0,1,2这种给法
//这种情况下就不需要使用newNode函数了


//树的先根遍历
void preorder(int root)
{
    cout<<Node[root].data;
    for(int i=0;i<Node[root].child.size();i++)
        preorder(Node[root].child[i]);
}

//https://blog.csdn.net/weixin_39485901/article/details/89236862 数组用法

//树的层序遍历
void LayerOrder(int root){
    queue<int> Q;
    Q.push(root);
    while(!Q.empty())
    {
        int front = Q.front();
        cout<<Node[front].data;
        Q.pop();
        for(int i =0 ;i < Node[front].child.size();i++)
            Q.push(Node[front].child[i]);
    }
}
/*P307
给定一棵树和每个结点的权值,求所有从根节点到叶子节点的路径,使得每条路径上的结点
的权值纸盒等于给定的常数S。如果有多条这样的路径,则按路径非递增的顺序输出。
令结构体node存放结点的数据域和指针域,其中指针域使用vector存放所有孩子结点的编号。
权值从大到小排序,读入的时候就把vector的结点从大到小,就能优先遍历大。
递归过程伪代码:
若sum > s,直接return
若sum = s,输出path[]
若sum < s,枚举所有当前访问结点idx的所有子结点,对每一个子节点child,先将其存入path[numNode],
然后利用递归参数child , numNode + 1 , sum + node[child].weight 往下一层递归 。 */

#include<bits/stdc++.h>
using namespace std;
const int N =110;

struct node{
    int weight;
    vector<int> child;               //vector<int> child储存结点的代号,和idx存储的是一个东西
}Node[N];                            //为什么?因为考试里的题往往都给了下标,不是idx++那个方向

bool cmp(int a,int b){
    return Node[a].weight>Node[b].weight;
}
int n,m,s;
int path[N];

void DFS(int idx,int numNode,int sum){
    if(sum > s) return;
    if(sum == s){
        if(Node[idx].child.size()!=0) return;
        for(int i = 0;i<numNode;i++){
            printf("%d",Node[path[i]].weight);
            if(i < numNode - 1) printf(" ");
            else printf("\n");
        }
        return;
    }
    for(int i=0;i < Node[idx].child.size();i++){
        int child = Node[idx].child[i];
        path[numNode] = child;
        DFS(child  , numNode + 1 , sum + Node[child].weight );
    }
}

//这个题处理输入也有点麻烦
int main(){
    scanf("%d%d%d".&n,&m,&S);
    for(int i=0;i<n;i++){
        scanf("%d%d",&id,&k);
        for(int j =0;j<k;j++){
            scanf("%d",&child);
            Node[id].child.push_back(child);
        }
        sort(Node[id].child.begin(),Node[id].child.end(),cmp);
    }
    path[0] = 0;
    DFS(0,1,Node[0].weight);
    return 0;
}



Loopback127
3个月前

#include<bits/stdc++.h>
using namespace std;

node tree[N];
int idx;
node* create()
{
    tree[idx].lchild=tree[idx].rlchild=NULL;
    return &tree[idx++];
}

typedef struct Node
{
    int data;
    node* lchild;
    node* rchild;
}node;

node* insert(node* root,int x)
{
    if(!root)
    {
        root=create();
        root->data=x;
    }
    else
    {
        if(root->data>x)
            root->lchild=insert(root->lchild,x);
        else
            root->rchild=insert(root->rchild,x);
    }
}



活动打卡代码 AcWing 854. Floyd求最短路

Loopback127
3个月前
#include<bits/stdc++.h>
using namespace std;

const int N=210,INF =1e9;

int n,m,Q;
int d[N][N];

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

int main()
{
    scanf("%d%d%d",&n,&m,&Q);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) d[i][j] = 0;
            else d[i][j]=INF;

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        d[a][b]=min(d[a][b],c);
    }

    floyd();

    while(Q--)
    {
        int a,b;
        int t= d[a][b];
        if(t>INF/2)puts("impossible";)
    }
}



Loopback127
3个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 510,INF=0x3f3f3f3f;


int g[N][N];
int dist[N];
int n,m;
bool st[N];

int prim()
{
    memset(dist,0x3f,sizeof dist);
    int res=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if((t==-1||dist[j]<dist[t])&&!st[j])
                t=j;
        }
        if(i&&dist[t]==INF) return INF;

        st[t]=true;

        if(i) res+=dist[t];

        for(int j=1;j<=n;j++)//注意这里更新所有边是更新到整体的距离,和dijkstra不一样 
            dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}



Loopback127
3个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    cout << dijkstra() << endl;

    return 0;
}





Loopback127
3个月前
//用queue做的,照着yls的模拟队列修改了代码
#include<bits/stdc++.h>
using namespace std;
const int N=100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];//d[]存储入度

int record[N],c;

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

bool toposort()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(!d[i])
            q.push(i);

    while(q.size())
    {
        int t=q.front();
        q.pop();
        record[c++]=t;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(--d[j]==0)
                q.push(j);

        }
    }
    if(c==n) return true;
    else return false;
}
int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);

        d[b] ++ ;
    }



    if(toposort())
       for(int i=0;i<c;i++)
            printf("%d ",record[i]);
    else
        cout<<-1<<endl;



    return 0;
}


活动打卡代码 AcWing 845. 八数码

Loopback127
3个月前
#include<bits/stdc++.h>
using namespace std;
const int N= 100010;

int bfs(string state)   //本题只有x能动,而且只能上下左右动,所以用bfs做
{
    queue<string> q;
    unordered_map<string, int> d;  //map d用来存储字符串对应到distance的映射

    q.push(state);
    d[state] = 0;

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

    string end ="12345678x";

    while(q.size())
    {
        auto t=q.front();
        q.pop();

        if(t==end) return d[t];

        int distance =d[t];

        //BFS经典for语句,遍历所有的'走法',树里是遍历邻接表
        //这里是遍历所有的方向、
        for(int i=0;i<4;i++)
        {
            int a = x+dx[i],b=y+dy[i];
            if(a>=        。。。)
            //这里是满足条件后,进入修改操作
            //满足条件交换
            //修改结果数组
            //把节点压入队列,准备下次使用

        }
        //恢复原样,因为要尝试4个方向
    }
        int k=t.find('x');  //find('x')函数返回字符x的下标
        int x=k/3,y=k%3;   //找到x在矩阵里的位置
        for(int i=0;i<4;i++)
        {
            int a = x+dx[i],b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3)
            {
                swap(t[a*3+b],t[k]);
                if(!d.count(t))    //不回头,d.count(t)查询状态t是否出现过
                {
                    d[t]=distance+1;
                    q.push(t);
                }
                swap(t[a*3+b],t[k]); //恢复
            }
        }
    }
    return -1;
}
int main()
{
    char s[2];

    string state;
    for (int i = 0; i < 9; i ++ )
    {
        cin >> s;
        state += *s;
    }

    cout << bfs(state) << endl;

    return 0;
}



活动打卡代码 AcWing 843. n-皇后问题

Loopback127
3个月前

#include<bits/stdc++.h>
using namespace std;
const int N=20;



int n;
bool col[N],dg[N],udg[N];
char g[N][N];


void dfs(int u){         //按照行u来遍历,i代表的是col列
    if(u==n)
    {
        for(int i=0;i<n;i++) puts(g[i]);
        cout<<endl;
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            if(!col[i]&&!dg[u+i]&&!udg[i-u+n])
            {
                col[i]=dg[u+i]=udg[i-u+n]=true;
                g[u][i]='Q';
                dfs(u+1);
                g[u][i]='.';
                col[i]=dg[u+i]=udg[i-u+n]=false;
            }
        }
    }
}
int main(){
    cin>>n;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';

    dfs(0);
    return 0;
}



Loopback127
3个月前
#include<bits/stdc++.h>
using namespace std;
const int N =200010;

int idx,n,m;
int e[N],ne[N],h[N];
int color[N];

bool dfs(int u,int c)
{
    color[u]=c;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!color[j])
        {
            if(!dfs(j,3-c)) return false;
        }
        else if(color[j]==c) return false;
    }
    return true;
}
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    bool flag =true;
    for(int i=1;i<=n;i++)
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                flag=false;
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}