个人空间 - AcWing

lzxzz

关注数

粉丝数

阅读量

1302

+关注发消息

离线：17小时前

活动打卡代码 AcWing 175. 电路维修

lzxzz
1天前

                #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 510,M=N*N;
#define x first
#define y second
char g[N][N];
int n,m;
int dist[N][N];
bool st[N][N];
int bfs()
{
    memset(st,0,sizeof st);
    memset(dist,0x3f,sizeof dist);
    deque<PII> q;
    dist[0][0]=0;
    q.push_back({0,0});
    int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1},di[]={-1,-1,0,0,},dj[]={-1,0,0,-1};
    string ss="\\/\\/";
    while(!q.empty())
    {
        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||b<0||a>n||b>m)continue;

            int ca=x+di[i],cb=y+dj[i];
            int d=dist[x][y]+int(g[ca][cb]!=ss[i]);
            if(d<dist[a][b])
            {
                dist[a][b]=d;
                if(g[ca][cb]!=ss[i])q.push_back({a,b});
                else q.push_front({a,b});
            }
        }
    }
    return dist[n][m];
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)cin>>g[i];

        if(n+m&1)
        puts("NO SOLUTION");
        else 
        cout<<bfs()<<endl;
    }

}

            

活动打卡代码 AcWing 173. 矩阵距离

lzxzz
1天前

                #include<bits/stdc++.h>
using namespace std;
const int N=1010,M=N*N;
typedef pair<int ,int >PII;
PII q[M];
#define x first
#define y second
int g[N][N];
int st[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int hh=0,tt=-1;
int n,m;
int main()
{
    memset(st,-1,sizeof st);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            scanf("%1d",&g[i][j]);
            if(g[i][j]==1)
            {
                //cout<<i<<' '<<j<<endl;
                q[++tt]={i,j};
                st[i][j]=0;
            }
        }
    while(hh<=tt)
    {
        auto t=q[hh++];

        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||b<0||a>=n||b>=m||st[a][b]!=-1)continue;
            q[++tt]={a,b};
            st[a][b]=st[t.x][t.y]+1;
            //cout<<a<<' '<<b<<endl;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        cout<<st[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

            

活动打卡代码 AcWing 1100. 抓住那头牛

lzxzz
1天前

                #include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int st[N];
int n,m;
int q[N];
void bfs()
{
    int hh=0,tt=0;
    q[0]=n;
    st[n]=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        if(st[m]!=-1) return ;

        if(t+1<N&&st[t+1]==-1)
        {
            q[++tt]=t+1;
            st[t+1]=st[t]+1;
        }
        if(t-1>=0&&st[t-1]==-1)
        {
            q[++tt]=t-1;
            st[t-1]=st[t]+1;
        }
        if(t*2<N&&st[t*2]==-1)
        {
            q[++tt]=t*2;
            st[t*2]=st[t]+1;
        }
    }
}
int main()
{
    memset(st,-1,sizeof st);
    cin>>n>>m;
    bfs();
    cout<<st[m]<<endl;
}

            

活动打卡代码 AcWing 188. 武士风度的牛

lzxzz
1天前

                scanf会读入换行？？？？？？
#include<bits/stdc++.h>
using namespace std;
const int N= 160,M=N*N;
typedef pair<int ,int > PII;
#define x first 
#define y second
int n,m;
PII q[M];
int dx[]={-1,-2,-2,-1,1,2,2,1},dy[]={-2,-1,1,2,2,1,-1,-2};
char g[N][N];
PII stt,ed;
int st[N][N];
void bfs()
{
    int hh=0,tt=0;
    q[0]=stt;
    st[stt.x][stt.y]=0;
    while(hh<=tt)
    {
        if(st[ed.x][ed.y]!=-1)
        return ;
        auto t=q[hh++];
        for(int i=0;i<8;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||b<0||a>=n||b>=m||st[a][b]!=-1)continue;
            if(g[a][b]!='*')
            {
                q[++tt]={a,b};
                st[a][b]=st[t.x][t.y]+1;
            }
        }
    }
}
int main()
{
    memset(st,-1,sizeof st);
    cin>>m>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            //cin>>g[i][j];
            scanf("%c",&g[i][j]);
            if(g[i][j]=='\n')
            scanf("%c",&g[i][j]);
            if(g[i][j]=='K')
            {
                stt={i,j};
                //cout<<i<<' '<<j<<endl;
            }
            if(g[i][j]=='H')
            {
                ed={i,j};
                //cout<<i<<' '<<j<<endl;
            }
        }
    }
    //cout<<ed.x<<' '<<ed.y<<endl;
    bfs();
    cout<<st[ed.x][ed.y];
}

            

活动打卡代码 AcWing 1076. 迷宫问题

lzxzz
1天前

                #include<bits/stdc++.h>
using namespace std;
const int N=1010,M=N*N;
#define x first 
#define y second
int g[N][N];
int n,root;
bool st[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
struct P
{
    int x,y,pre;
}q[M];
void bfs(int x,int y)
{
    int hh=0,tt=0;
    q[0]={0,0,-1};
    st[x][y]=true;
    while(hh<=tt)
    {
        auto t=q[hh++];
        if(t.x==n-1&&t.y==n-1)root=hh-1;
        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||b<0||a>=n||b>=n||st[a][b]) continue;
            if(g[a][b]==0)
            {
            q[++tt]={a,b,hh-1};
            st[a][b]=true;
            }
        }
    }
}
void print(int x)
{
    if(q[x].pre!=-1)
    print(q[x].pre);
    cout<<q[x].x<<' '<<q[x].y<<endl;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    cin>>g[i][j];

    bfs(0,0);
    print(root);
}

            

活动打卡代码 AcWing 1106. 山峰和山谷

lzxzz
1天前

                #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second 
const int N=1010,M=N*N;
int g[N][N];
int n;
bool st[N][N];
PII q[M];
void bfs(int x,int y,bool & high,bool &low)
{
    int hh=0,tt=0;
    q[0]={x,y};
    st[x][y]=true;
    while(hh<=tt)
    {
        auto t=q[hh++];
        for(int i=-1;i<2;i++)
            for(int j=-1;j<2;j++)
            {
                if(i==0&&j==0)continue;
                int a=t.x+i,b=t.y+j;
                if(a<0||b<0||a>=n||b>=n) continue;
                if(g[t.x][t.y]!=g[a][b])
                {
                    if(g[t.x][t.y]<g[a][b]) high=true;
                    else low=true;
                }
                else if(!st[a][b])
                {
                    q[++tt]={a,b};
                    st[a][b]=true;
                }
            }
    }
}
int main()
{
    int x=0,y=0;
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            if(!st[i][j])
            {
                bool a=false,b=false;//高低
                bfs(i,j,a,b);
                if(!a)x++;
                if(!b)y++;
            }
        }
    cout<<x<<' '<<y<<endl;
}

            

活动打卡代码 AcWing 1098. 城堡问题

lzxzz
2天前

                #include<bits/stdc++.h>
using namespace std;
const int N=60;
#define x first
#define y second 
typedef pair<int ,int > PII;
PII q[N*N];
int g[N][N],ans,s;
int n,m,dx[4]={0,-1,0,1},dy[]={-1,0,1,0};
bool st[N][N];
int bfs(int x,int y)
{
    int hh=0,tt=0,s=0;
    q[0]={x,y};
    st[x][y]=true;
    while(hh<=tt)
    {
        auto t=q[hh++];
        s++;
        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||b<0||a>=n||b>=m) continue;
            if(st[a][b])continue;
            if(g[t.x][t.y]>>i&1)continue;
                q[++tt]={a,b};
                st[a][b]=true;
        }
    }
    return s;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(!st[i][j])
            {
                s=max(s,bfs(i,j));
                ans++;
            }
    cout<<ans<<endl<<s<<endl;
}

            

活动打卡代码 AcWing 1097. 池塘计数

lzxzz
2天前

                #include<bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
int n,m;
int ans;
int dx[4]={-1,0,1,0},dy[]={0,1,0,-1};
void dfs(int x,int y)
{
    g[x][y]='.';
    for(int j=-1;j<2;j++)
    for(int i=-1;i<2;i++)
    {
        int q=x+i,w=y+j;
        if(q>=0&&w>=0&&q<n&&w<m&&g[q][w]=='W')
        dfs(q,w);
    }
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>g[i];

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        if(g[i][j]=='W')
        {
        dfs(i,j);
        ans++;
        }
        cout<<ans<<endl;
}

            

活动打卡代码 AcWing 302. 任务安排3

lzxzz
2天前

                #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N= 3e5+10;
ll c[N],t[N];
ll n,s,f[N];
int q[N];
int main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i]>>c[i];
        c[i]+=c[i-1];
        t[i]+=t[i-1];
    }
    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        int l=hh,r=tt;
        while(l<r)
        {
            int mid=l+r>>1;
            if((f[q[mid+1]]-f[q[mid]])>(t[i]+s)*(c[q[mid+1]]-c[q[mid]]))r=mid;
            else l=mid+1;
        }
        int j=q[l];
        f[i]=f[j]-(t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
        while(hh<tt&& double(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt-1]])>=double(f[i]-f[q[tt-1]])*(c[q[tt]]-c[q[tt-1]]))tt--;
        q[++tt]=i;
    }

    cout<<f[n]<<endl;


}

            

活动打卡代码 AcWing 301. 任务安排2

lzxzz
2天前

                #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N= 3e5+10;
ll c[N],t[N];
ll n,s,f[N];
int q[N];
int main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i]>>c[i];
        c[i]+=c[i-1];
        t[i]+=t[i-1];
    }
    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        while(hh<tt&& (f[q[hh + 1]] - f[q[hh]]) <=(t[i]+s)*(c[q[hh+1]]-c[q[hh]]))hh++;
        int j=q[hh];
        f[i]=f[j]-(t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
        while(hh<tt&& (f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt-1]])>=(f[i]-f[q[tt-1]])*(c[q[tt]]-c[q[tt-1]]))tt--;
        q[++tt]=i;
    }

    cout<<f[n]<<endl;


}

            

0 评论

0 评论

0 评论

scanf会读入换行？？？？？？

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论