头像

wyzde18

山东大学




在线 


最近来访(111)
用户头像
浪什么花
用户头像
L_52
用户头像
樱落二瓣七里香
用户头像
VegeDog
用户头像
har
用户头像
zsl_cs
用户头像
CZL
用户头像
CQH130
用户头像
梦忆晴天
用户头像
Refrain_c
用户头像
wqy2022
用户头像
该账号被封禁AcWing
用户头像
像野草一样倔强
用户头像
Barbed
用户头像
Thresh
用户头像
像野花一样坚强
用户头像
坠落的余晖
用户头像
MousePotatoes
用户头像
拾光010
用户头像
不灭孽蜥

活动打卡代码 AcWing 1113. 红与黑

wyzde18
11小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 25;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n,m;
char g[N][N];
bool st[N][N];

int dfs(int x,int y)
{
    int cnt=1;
    st[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(x<0||x>=n||y<0||y>=m) continue;
        if(st[a][b]) continue;
        if(g[a][b]!='.') continue;
        cnt+=dfs(a,b);
    }
    return cnt;
}

int main()
{
    while(cin>>m>>n,n||m)
    {
        int x,y;
        memset(st, 0, sizeof st);
        for(int i=0;i<n;i++)
            scanf("%s",g[i]);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(g[i][j]=='@')
                x=i,y=j;
            }
        cout<<dfs(x,y)<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1112. 迷宫

wyzde18
12小时前
#include<iostream>
#include<cstring>

using namespace std;
const int N = 110;

int n;
int sx,sy,fx,fy;
char g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};



int dfs(int x,int y)
{
    if(g[x][y]=='#') return false;
    if(x==fx&&y==fy) return true;

    st[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int ux=x+dx[i],uy=y+dy[i];
        if(ux<0||ux>=n||uy<0||uy>=n) continue;
        if(st[ux][uy]) continue;
        if(dfs(ux,uy)) return true;
    }
    return false;
}


int main()
{
    int k;
    cin>>k;
    while(k--)
    {
        memset(st, 0, sizeof st);
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%s",g[i]);
        cin>>sx>>sy>>fx>>fy;
        if(dfs(sx,sy)) puts("YES");
        else puts("NO");
    }
    return 0;
}


活动打卡代码 AcWing 178. 第K短路

wyzde18
13小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>

#define x first
#define y second

using namespace std;
const int N = 1010,M=100010;
typedef pair<int, int> PII;
typedef pair<int,PII> PIII;

int n,m;
int h[N],rh[N],e[M],ne[M],w[M],idx;
int S,T,K;
int dist[N];
bool st[N];
int cnt[N];

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

void dijsktra()
{
    memset(dist,0x3f,sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,T});
    dist[T]=0;
    while(heap.size())
    {
        PII t=heap.top();
        heap.pop();
        int ver=t.second;
        if(st[ver]) continue;
        st[ver]=true;
        for(int i=rh[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[ver]+w[i])
            {
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}

int Astar()
{
    if(dist[S]==0x3f3f3f3f) return -1;
    priority_queue<PIII,vector<PIII>,greater<PIII>> heap;//第一个存估计距离,第二个实际距离,第三个存坐标
    heap.push({dist[S],{0,S}});
    while(heap.size())
    {
        PIII t=heap.top();
        heap.pop();
        int ver=t.y.y,distance=t.y.x;
        cnt[ver]++;
        if(cnt[T]==K) return distance;
        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            heap.push({distance+w[i]+dist[j],{distance+w[i],j}});
        }
    }
    return -1;
}

int main()
{
    memset(h, -1, sizeof h);
    memset(rh,-1,sizeof rh);
    scanf("%d%d",&n,&m);
    while (m -- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(h,a,b,c);
        add(rh,b,a,c);
    }
    scanf("%d%d%d",&S,&T,&K);
    if (S == T) K ++ ;//自己到自己肯定有一条距离为0的边.因为最短路要包含一条边,所以把这条边删去,也就是让k++;
    dijsktra();
    cout<<Astar()<<endl;
}


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

wyzde18
16小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

typedef pair<int,string> PIS;

string st,ed,seg;
unordered_map<string,int> dist;
unordered_map<string,pair<string,char>> pre;
priority_queue<pair<int,string>,vector<PIS>,greater<PIS>> heap;

int f(string state)
{
    int res=0;
    for(int i=0;i<state.size();i++)
        if(state[i]!='x')
        {
            int t=state[i]-'1';
            res+=abs(i/3-t/3)+abs(i%3-t%3);
        }
    return res;
}

string bfs()
{
    ed="12345678x";
    char op[]={'u','d','l','r'};
    int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
    heap.push({f(st),st});
    dist[st]=0;
    while(heap.size())
    {
        PIS t=heap.top();
        heap.pop();
        string state=t.second;
        if(state==ed) break;
        int x,y;
        for(int i=0;i<state.size();i++)
            if(state[i]=='x') 
            {
                x=i/3,y=i%3;
                break;
            }
        int d=dist[state];
        string source=state;
        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) continue;
            swap(state[x*3+y],state[a*3+b]);
            if(!dist[state]||dist[state]>d+1)
            {
                dist[state]=d+1;
                heap.push({f(state)+dist[state],state});
                pre[state]={source,op[i]};
            }
            swap(state[x*3+y],state[a*3+b]);
        }
    }


    string res;
    while(ed!=st)
    {
        res+=pre[ed].second;
        ed=pre[ed].first;
    }
    reverse(res.begin(),res.end());
    return res;
}


int main()
{
    string c;
    while(cin>>c)
    {
        st+=c;
        if(c!="x") seg+=c;
    }
    int cnt=0;
    for(int i=0;i<8;i++)
        for(int j=i+1;j<8;j++)
            if(seg[i]>seg[j]) cnt++;
    if(cnt&1) puts("unsolvable");
    else cout<<bfs()<<endl;
    return 0;
}


活动打卡代码 AcWing 190. 字串变换

wyzde18
20小时前
#include<iostream>
#include <queue>
#include<cstring>
#include<unordered_map>

using namespace std;
const int N = 6;

int n;
string A,B;
string a[N],b[N];

int extend(queue<string>& qa,unordered_map<string,int>& da,unordered_map<string,int>& db,string a[N],string b[N])
{
    int d=da[qa.front()];
    while(qa.size()&&d==da[qa.front()])
    {
        string t=qa.front();
        qa.pop();
        for(int i=0;i<n;i++)
            for(int j=0;j<t.size();j++)
            {
                if(t.substr(j,a[i].size())==a[i])
                {
                    string r=t.substr(0,j)+b[i]+t.substr(j+a[i].size());
                    if(db.count(r)) return da[t]+db[r]+1;
                    if(da.count(r)) continue;
                    da[r]=da[t]+1;
                    qa.push(r);
                }
            }
    }
    return 11;
}


int bfs()
{
    if(A==B) return 0;
    queue<string> qa,qb;
    unordered_map<string,int> da,db;
    qa.push(A),qb.push(B);
    da[A]=0,db[B]=0;
    int step=0;
    while(qa.size()&&qb.size())
    {
        int t;
        if(qa.size()<=qb.size()) t=extend(qa,da,db,a,b);
        else t=extend(qb,db,da,b,a);
        if(t<=10) return t;
        if(++step==10) return -1;
    }
    return -1;
}




int main()
{
    cin>>A>>B;
    while(cin>>a[n]>>b[n]) n++;
    int t=bfs();
    if(t==-1) puts("NO ANSWER!");
    else 
        printf("%d\n",t);
    return 0;
}


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

wyzde18
23小时前
#include<iostream>
#include<deque>
#include<cstring>
#include<algorithm>

#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 510;

int n,m;
char g[N][N];
int dist[N][N];;
deque<PII> q;

int bfs()
{
    memset(dist,0x3f,sizeof dist);
    q.push_front({0,0});
    dist[0][0]=0;
    int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1};
    int ix[]={-1,-1,0,0},iy[]={-1,0,0,-1};

    char s[]="\\/\\/";

    while(q.size())
    {
        PII t=q.front();
        q.pop_front();
        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            int aa=t.x+ix[i],bb=t.y+iy[i];
            if(a<0||a>n||b<0||b>m) continue;
            int d = dist[t.x][t.y]+(g[aa][bb]!=s[i]);
            if (d < dist[a][b])
            {
                dist[a][b] = d;

                if (g[aa][bb] != s[i]) q.push_back({a, b});
                else q.push_front({a, b});
            }
        }
    }
    return dist[n][m];
}


int main()
{   int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
        if((n+m)%2==1) 
        {
            puts("NO SOLUTION");
            continue;
        }                
        cout<<bfs()<<endl;
    }
    return 0;
}




活动打卡代码 AcWing 1107. 魔板

wyzde18
1天前
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<unordered_map>

using namespace std;

string st,fn;
unordered_map<string,int> dist;
unordered_map<string,pair<char,string>> pre;

string move0(string a)
{
    string res=a;
    for(int i=0;i<=3;i++)
        swap(res[i],res[7-i]);
    return res;
}


string move1(string a)
{
    string res=a;
    for(int i=3;i>=1;i--) swap(res[i],res[i-1]);
    for(int i=4;i<=6;i++) swap(res[i],res[i+1]);
    return res;
}

string move2(string a)
{
    string res=a;
    swap(res[1],res[2]);
    swap(res[1],res[5]);
    swap(res[1],res[6]);
    return res;
}

int bfs(string st,string fn)
{
    if(st==fn) return 0;
    queue<string> q;
    q.push(st);
    dist[st]=0;
    while(q.size())
    {
        string t=q.front();
        q.pop();
        string m[3];
        m[0]=move0(t);
        m[1]=move1(t);
        m[2]=move2(t);
        for(int i=0;i<=2;i++)
        {
            if(!dist.count(m[i]))
            {
                q.push(m[i]);
                pre[m[i]]={i+'A',t};
                dist[m[i]]=dist[t]+1;
                if(m[i]==fn) return dist[fn];
            }
        }
    }

}

int main()
{

    for(int i=1;i<=8;i++)
        st+=i+'0';
    for(int i=1;i<=8;i++)
    {
        int x;
        cin>>x;
        fn+=x+'0';
    }
    int cnt=bfs(st,fn);
    cout<<cnt<<endl;
    string res;
    while(fn!=st)
    {
        res+=pre[fn].first;
        fn=pre[fn].second;
    }
    reverse(res.begin(),res.end());
    if(cnt>0)
        cout<<res<<endl;
    return 0;
}


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

wyzde18
2天前
#include<iostream>
#include<cstring>
#include<algorithm>

#define x first 
#define y second

using namespace std;
typedef pair<int,int> PII;
const int N=1010,M=N*N;

char g[N][N];
int dist[N][N];
PII q[M];
int n,m;

void bfs()
{
    memset(dist,-1,sizeof dist);
    int dx[]={-1,0,1,0};
    int dy[]={0,1,0,-1};
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(g[i][j]=='1')
            {
                q[++tt]={i,j};
                dist[i][j]=0;
            }
        }
    while(hh<=tt)
    {
        PII t=q[hh++];
        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i];
            int b=t.y+dy[i];
            if(a<1||a>n||b<1||b>m) continue;
            if(dist[a][b]!=-1) continue;
            q[++tt]={a,b};
            dist[a][b]=dist[t.x][t.y]+1;
        }
    }
}


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%s",g[i]+1);
    bfs();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d ",dist[i][j]);
        cout<<endl;
    }
    return 0;
}


新鲜事 原文

wyzde18
2天前
嘉然的百万分纪念直播真的绝绝子


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

wyzde18
2天前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=2e5+10;

int n,k;
int dist[N];
int q[N];

int bfs()
{
    memset(dist,-1,sizeof dist);
    int tt=-1,hh=0;
    q[++tt]=n;
    dist[n]=0;
    while(hh<=tt)
    {
        int now=q[hh++];
        if(now==k) return dist[now];
        if(now-1>=0&&dist[now-1]==-1)
        {
            q[++tt]=now-1;
            dist[now-1]=dist[now]+1;
        }
        if(now+1<N&&dist[now+1]==-1)
        {
            q[++tt]=now+1;
            dist[now+1]=dist[now]+1;
        }
        if(now*2<N&&dist[now*2]==-1)
        {
            q[++tt]=now*2;
            dist[now*2]=dist[now]+1;
        }
    }
}

int main()
{
    cin>>n>>k;
    cout<<bfs()<<endl;
    return 0;
}