头像

WUHUQIFEI123




在线 


最近来访(21)
用户头像
辣鸡号航母
用户头像
WA声闹彻明
用户头像
垫底抽風
用户头像
YuWindSky
用户头像
JcWing
用户头像
howerguss
用户头像
牧濑红莉栖
用户头像
NZX
用户头像
城主
用户头像
RNGriri
用户头像
今天学英语了嘛
用户头像
一页知秋
用户头像
acwing_8869
用户头像
Abel51
用户头像
codemoe
用户头像
coolguy1234
用户头像
末那

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

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

#define x first
#define y second

using namespace std;

typedef pair<int, string> PIS;

int f(string state){
    int  res = 0;

    for(int i = 0; i < 9; 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(string start){
    int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
    char op[] = "udlr";
    string end = "12345678x";

    priority_queue<PIS, vector<PIS>, greater<PIS>> q;
    unordered_map<string, int> dist;
    unordered_map<string, pair<string,char>> pre;

    q.push({f(start), start});
    dist[start] = 0;

    while(q.size()){
        PIS t = q.top();
        q.pop();

        if(t.y == end) break;
        int step = dist[t.y];
        int x1, y1;

        for(int i = 0; i < 9; i ++){
            if(t.y[i] == 'x'){
                x1 = i/3, y1 = i%3;
                break;
            }
        }

        string st = t.y;

        for(int i = 0; i < 4; i ++){
            int a = x1+dx[i], b = y1+dy[i];
            if(a < 0|| b < 0|| a >= 3|| b >= 3) continue;
            swap(t.y[x1*3+y1], t.y[a*3+b]);
            if(!dist.count(t.y) || dist[t.y] > step + 1){
                dist[t.y] = step + 1;
                pre[t.y] = {st, op[i]};
                q.push({f(t.y)+dist[t.y],t.y});

            }
            swap(t.y[x1*3+y1], t.y[a*3+b]);
        }
    }

    string res, zheng;

    while(end != start){
        res += pre[end].y;
        end = pre[end].x;
    }

    for(int i = res.size()-1; i >= 0; i --) zheng += res[i];

    return zheng;

}



int main(){

    char c;
    string start, prev;
    for(int i = 0; i < 9; i ++){
        cin>>c;
        start += c;
        if(c != 'x') prev += c;
    }

    int cnt = 0;

    for(int i = 0; i < 8; i ++){
        for(int j = i+1; j < 8; j ++){
            if(prev[i] > prev[j]) cnt ++;
        }
    }

    if(cnt%2) puts("unsolvable");
    else cout<<bfs(start)<<endl;

    return 0;
}


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

WUHUQIFEI123
21小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

const int N = 6;

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

int extend(queue<string> &q, unordered_map<string, int>& da, unordered_map<string, int>& db,  string a[], string b[]){
    int d = da[q.front()];
    while(q.size() && da[q.front()] == d){
        string t = q.front();
        q.pop();
        for(int i = 0; i < t.size(); i ++){
            for(int j = 0; j < n; j ++){


                if(t.substr(i, a[j].size()) == a[j]){
                    string s = t.substr(0, i) + b[j] + t.substr(i+a[j].size());
                    if(db.count(s)) return da[t] + 1+db[s];
                    if(da.count(s)) continue;
                    da[s] = da[t] + 1;
                    q.push(s);
                }
            }
        }

    }

    return 11;

}

int bfs(string A, string B){
    if(A == B) return 0;
    queue<string> qa, qb;
    unordered_map<string, int> da, db;
    qa.push(A), da[A] = 0;
    qb.push(B), 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 11;
    }


    return 11;
}

int main(){

    string A, B;
    cin>>A>>B;

    while(cin>>a[n]>>b[n]) n ++;

    int step = bfs(A, B);

    if(step >= 11) puts("NO ANSWER!");
    else printf("%d\n", step);

    return 0;
}


活动打卡代码 AcWing 1153. 括号树

#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 501000;

ll f[N], g[N], ans;
int e[N], ne[N], idx, h[N];
int n, a[N], stk[N], top;
char str[N];

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

void dfs(int u){
    if(str[u] == '('){
        stk[++top] = u;
        f[u] = f[a[u]];
        for(int i = h[u]; i != -1; i = ne[i]) dfs(e[i]);
        -- top;
    }
    else{
        if(!top){
            f[u] = f[a[u]];
            for(int i = h[u]; i != -1; i = ne[i]) dfs(e[i]);
        }
        else{
            int t = stk[top--];
            g[u] = g[a[t]] + 1;
            f[u] = f[a[u]] + g[u];
            for(int i = h[u]; i != -1; i = ne[i]) dfs(e[i]);
            stk[++top] = t;
        }
    }
}

int main(){

    cin>>n;
    cin>>str+1;

    memset(h, -1, sizeof h);

    for(int i = 2; i <= n; i ++ ){
        cin>>a[i];
        add(a[i], i);
    }

    dfs(1);

    for(int i = 1; i <= n; i ++){
        ans ^= f[i]*i;
    }

    cout<<ans<<endl;


    return 0;
}


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

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 510;

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

int bfs(){
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[0][0] = 0;
    deque<PII> q;
    q.push_back({0,0});

    int dx[] = {-1,-1,1,1}, dy[] = {-1,1,-1,1};
    int ix[] = {-1,-1,0,0}, iy[] = {-1,0,-1,0};
    char s[6] = "\\//\\";

    while(q.size()){
        PII t = q.front();
        q.pop_front();

        if(t.x == n && t.y == m) return dist[n][m];

        if(st[t.x][t.y]) continue;
        st[t.x][t.y] = true;

        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;
            int ga = t.x + ix[i], gb = t.y + iy[i];
            int w = dist[t.x][t.y] + (g[ga][gb] != s[i]);
            if(w < dist[a][b]){
                dist[a][b] = w;
                if(g[ga][gb] != s[i]) q.push_back({a,b});
                else q.push_front({a,b});
            }

        }
    }

    return -1;
}

int main(){

    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;
    }

    return 0;
}


活动打卡代码 AcWing 1107. 魔板

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

char g[4][8];
unordered_map<string, int> dist;
queue<string> q;
unordered_map<string, pair<char, string>> pre;

void set(string str){
    for(int i = 0; i < 4; i ++) g[0][i] = str[i];
    for(int i = 3, j = 4; i >= 0; i --, j ++) g[1][i] = str[j];
}

string get(){
    string res;

    for(int i = 0; i < 4; i ++) res += g[0][i];
    for(int i = 3; i >= 0; i --) res += g[1][i];

    return res;
}

string move1(string str){
    set(str);
    for(int i = 0; i < 4; i ++) swap(g[0][i], g[1][i]);
    return get();
}

string move2(string str){
    set(str);

    char s1 = g[0][3];
    char s2 = g[1][3];


    for(int i = 3; i >= 1; i --){
        g[0][i] = g[0][i-1];
        g[1][i] = g[1][i-1];
    }
    g[0][0] = s1;
    g[1][0] = s2;
    return get();

}

string move3(string str){
    set(str);

    char s1 = g[0][1];
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = s1;


    return get();
}

int bfs(string start, string end){
    if(start == end) return 0;

    q.push(start);
    dist[start] = 0;

    while(!q.empty()){
        string t = q.front();
        q.pop();

        string m[3];
        m[0] = move1(t);
        m[1] = move2(t);
        m[2] = move3(t);

        for(int i = 0; i < 3; i ++){
            if(!dist.count(m[i])){
                string str = m[i];

                pre[str] = {i+'A', t};
                dist[str] = dist[t] + 1;
                if(str == end) return dist[t] + 1;
                q.push(str);
            }
        }
    }

    return -1;
}

int main(){

    int x;
    string start , end ; 

    for(int i = 0; i < 8; i ++){
        cin>>x;
        start += char(i+'1');
        end += char(x+'0');
    }

    int step = bfs(start, end);

    string res;
    cout<<step<<endl;

    while(end != start)
    {
        res += pre[end].first;
        end = pre[end].second;
    }

    reverse(res.begin(), res.end());

    if(step) cout<<res<<endl; 

    return 0;
}


活动打卡代码 AcWing 1152. 格雷码

#include <iostream>

using namespace std;

typedef unsigned long long ull;

int n;
ull k;

string f(ull n, ull k){
    if(!n) return "";
    if(k < (1ull <<n-1)) return "0"+f(n-1,k);
    ull t = (1ull <<n)-1;
    if(n == 64) t --;//如果超过64,那么会变成负数,只要再减掉一个1就可以了
    return "1" + f(n-1, t-k); 
}

int main(){
    cin>>n>>k;

    cout<<f(n, k)<<endl;

    return 0;
}   


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

#include <iostream>
#include <cstring>

#define x first
#define y second 

using namespace std;

const int N = 1100;

typedef pair<int, int> PII;

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

void bfs(){
    memset(dist, -1, sizeof dist);

    int hh = 0, tt = -1;
    for(int i = 0; i < n ;i ++ ){
        for(int j = 0; j < m; j ++){
            if(g[i][j] == '1') dist[i][j] = 0, q[++tt] = {i,j};//从每个起点开始找
        }
    }

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

    while(hh <= tt){
        PII 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 || dist[a][b] != -1) continue;
            dist[a][b] = dist[t.x][t.y] + 1;
            q[++tt] = {a,b};
        }
    }

}


int main(){

    cin>>n>>m;

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

        }

    }

    bfs();

    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j ++){
            cout<<dist[i][j]<<" ";
        }
        cout<<endl;

    }

    return 0;
}


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

#include <iostream>
#include <cstring>

using namespace std;

const int N = 200010;

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

int bfs(){
    int hh = 0, tt = 0;
    q[0] = n;
    memset(dist,-1, sizeof dist);
    dist[n] = 0;

    while(hh <= tt){
        int t = q[hh++];
        if(t + 1 < N && dist[t+1] == -1){
            dist[t+1] = dist[t] + 1;
            q[++tt] = t+1;
        }
        if(t - 1 >= 0 && dist[t-1] == -1){
            dist[t-1] = dist[t] + 1;
            q[++tt] = t-1;
        }
        if(t*2 < N && dist[t*2] == -1){
            dist[t*2] = dist[t] + 1;
            q[++tt] = t*2;
        }
    }

    return dist[k];
}

int main(){

    cin>>n>>k;

    cout<<bfs()<<endl;

    return 0;
}


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

#include <iostream>
#include <cstring>
#define x first 
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 160;

char g[N][N];
int d[N][N];
int n,m ;
PII q[N*N];

int bfs(){
    int ax = 0, ay = 0;

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

    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j++){
            if(g[i][j] == 'K') ax = i, ay = j;
        }
    }

    memset(d, -1, sizeof d);

    int hh = 0, tt = -1;
    q[++tt] = {ax, ay};
    d[ax][ay] = 0;

    while(hh <= tt){
        PII t = q[hh++];

        for(int i = 0; i < 8; i ++){
            int a = t.x+dx[i], b = t.y+dy[i];
            if(d[a][b] != -1) continue;
            if(a < 0|| b < 0|| a >= n|| b >= m || g[a][b] == '*') continue;
            if(g[a][b] == 'H') return d[t.x][t.y] + 1;
            d[a][b] = d[t.x][t.y] + 1;
            q[++tt] = {a,b};
        }

    }

    return -1;

}

int main(){

    cin>>m>>n;

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

    cout<<bfs()<<endl;



    return 0;
}


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

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1100;

int g[N][N];
int n;
PII pre[N][N], q[N*N];

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

void bfs(int ax, int ay){
    int hh = 0, tt = -1;
    q[++tt] = {ax, ay};
    memset(pre, -1, sizeof pre);//记录路径
    pre[ax][ax] = {0,0};//已经有值

    while(hh <= tt){
        PII 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 >= n) continue;
            if(pre[a][b].x != -1 || g[a][b]) continue;
            q[++tt] = {a,b};
            pre[a][b] = t;//记录上一个
        }
    }
}

int main(){

    cin>>n;

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

    bfs(n-1, n-1);
    PII end(0,0);

    while(true){
        cout<<end.x<<" "<<end.y<<endl;
        if(end.x == n-1 && end.y == n-1) break;
        end = pre[end.x][end.y];
    }

    return 0;
}