头像

有猷

姜堰四中


访客:7070

离线:4天前


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

有猷
4天前

蒟蒻的第一个A*代码~(在yxc老师的讲解下终于学会了)

#include<iostream>
#include<queue>
#include<map>
using namespace std;
#define re register
#define Re register
char tar[4][4] = {
    0,0,0,0,
    0,'1','2','3',
    0,'4','5','6',
    0,'7','8','x',
};
int check[10],idx;
int dx[5] = {-1,1,0,0};
int dy[5] = {0,0,-1,1};
string ds[5] = {"u","d","l","r"};
struct node{
    int f,x,y,t;
    char ch[4][4];
    string s;
}st;
bool operator<(node a,node b){
    return a.t + a.f > b.t + b.f;
}
priority_queue<node>q;
map<int,bool>m;
int F(node x){
    int res = 0;
    for(re int i = 1;i <= 3;i++){
        for(re int j = 1;j <= 3;j++){
            if(x.ch[i][j] != 'x'){
                for(re int I = 1;I <= 3;I++){
                    for(re int J = 1;J <= 3;J++){
                        if(tar[I][J] == x.ch[i][j]){
                            res += abs(I - i) + abs(J - j);
                        }
                    }
                }
            }
        }
    }
    return res;
}
int get_s(node x){
    int res = 0;
    for(Re int i = 1;i <= 3;i++){
        for(Re int j = 1;j <= 3;j++){
            res = res * 10;
            if(x.ch[i][j] != 'x')res += x.ch[i][j] - '0';
        }
    }
    return res;
}
void bfs(){
    q.push(st);
    while(!q.empty()){
        node fr = q.top();
        q.pop();
        if(fr.f == 0){
            cout << fr.s << endl;
            exit(0);
        }
        for(re int i = 0;i < 4;i++){
            int nx = fr.x + dx[i],ny = fr.y + dy[i];
            if(nx > 3 || ny > 3 || nx < 1 || ny < 1)continue;
            node ne = fr;
            swap(ne.ch[fr.x][fr.y],ne.ch[nx][ny]);
            if(m[get_s(ne)])continue;
            m[get_s(ne)] = true;
            ne.s += ds[i];
            ne.f = F(ne);
            ne.x = nx;ne.y = ny;
            ne.t = fr.t + 1;
            q.push(ne);
        }
    }
}
int main() {
    for(re int i = 1;i <= 3;i++){
        for(re int j = 1;j <= 3;j++){
            cin >> st.ch[i][j];
            if(st.ch[i][j] == 'x'){
                st.x = i;
                st.y = j;
            }
            else check[++idx] = st.ch[i][j] - '0';
        }
    }
    int res = 0;
    for(re int i = 1;i <= 8;i++){
        for(re int j = 1;j < i;j++){
            res += (check[i] > check[j]);
        }
    }
    st.f = 1;
    if(res % 2 != 0){
        cout << "unsolvable" << endl;
        return 0;
    }
    bfs();
    return 0;
}


新鲜事 原文

有猷
10天前
图片


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

有猷
10天前

#include<iostream>
#include<string>
#include<queue>
#include<map>
using namespace std;
#define re register
#define Re register
string s1,s2,a[30],b[30];
int n;
queue<string>q1,q2;
map<string,int>ta,tb;
int extend(queue<string> &q,string a[],string b[],map<string,int> &t1,map<string,int> &t2){
    string fr = q.front();
    q.pop();
    int lens = fr.size();
    for(re int i = 0;i < lens;i++){
        for(re int j = 1;j <= n;j++){
            string tmp = fr.substr(i,a[j].size());
            if(tmp != a[j])continue;
            string r = fr.substr(0,i) + b[j] + fr.substr(i + a[j].size());
            if(t2.count(r))return t2[r] + t1[fr];
            if(t1.count(r))continue;
            t1[r] = t1[fr] + 1;
            q.push(r);
        }
    }
    return -1;
}
int bfs(){
    ta[s1] = 0;tb[s2] = 1;
    q1.push(s1);q2.push(s2);
    while(!q1.empty() && !q2.empty()){
        if(ta[q1.front()] + tb[q2.front()] > 10)break;
        int t;
        if(q1.size() < q2.size())t = extend(q1,a,b,ta,tb);
        else t = extend(q2,b,a,tb,ta);
        if(t != -1)return t;
    }
    cout << "NO ANSWER!" << endl;
    exit(0);
}
int main() {
    cin >> s1 >> s2;
    while(cin >> a[++n])
        cin >> b[n];
    cout << bfs() << endl;
    return 0;
}


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

有猷
13天前
#include<iostream>
#include<cstring>
using namespace std;
#define re register
#define Re register
#define MAXN 505
int T,r,c,h,t,vis[MAXN][MAXN];
struct node{
    int x,y,t;
}q[MAXN * MAXN * 2];
bool lft[505][505];
int dx[5] = {1,1,-1,-1};
int dy[5] = {1,-1,1,-1};
int ok[5] = {1,0,0,1};
int lx[5] = {0,0,1,1};
int ly[5] = {0,1,0,1};
void bfs(){
    h = t = 500 * 500;
    q[h] = (node){0,0,0};
    vis[0][0] = 0;
    while(h <= t){
        node fr = q[h];
        h++;
        if(fr.x == r && fr.y == c){
            cout << fr.t << endl;
            return;
        }
        for(Re int i = 0;i < 4;i++){
            int nx = fr.x + dx[i],ny = fr.y + dy[i];
            if(nx >= 0 && nx <= r && ny >= 0 && ny <= c && vis[nx][ny] > fr.t + (lft[nx + lx[i]][ny + ly[i]] != ok[i])){
                vis[nx][ny] = fr.t + (lft[nx + lx[i]][ny + ly[i]] != ok[i]);
                if(lft[nx + lx[i]][ny + ly[i]] != ok[i])q[++t] = (node){nx,ny,fr.t + 1};
                else q[--h] = (node){nx,ny,fr.t};
            }
        }
    }
    cout << "NO SOLUTION" << endl;
}
int main() {
    cin >> T;
    while(T--){
        cin >> r >> c;
        memset(vis,127,sizeof vis);
        for(re int i = 1;i <= r;i++){
            for(re int j = 1;j <= c;j++){
                char ch;
                cin >> ch;
                lft[i][j] = (ch == '\\');
            }
        }
        bfs();
    }
    return 0;
}


活动打卡代码 AcWing 1107. 魔板

有猷
17天前

这题很烦啊~考的是细心! 正是蒟蒻我所欠缺的

#include<iostream>
#include<queue>
#include<string>
#include<map>
using namespace std;
#define re register
#define Re register
int tar[10][10];
string s0;
struct node{
    int a[3][5];
    int t;
    string s;
}zero,n0;
map<int,bool>_m;
queue<node>q;
bool ok(node x){
    for(re int i = 1;i <= 4;i++){
        if(x.a[1][i] == tar[1][i] && x.a[2][i] == tar[2][i])continue;
        return false;
    }
    return true;
}
int get(node x){
    int cnt = 0;
    for(re int j = 1;j <= 4;j++){
        cnt = cnt * 10 + x.a[1][j];
    }
    for(Re int j = 4;j >= 1;j--){
        cnt = cnt * 10 + x.a[2][j];
    }
    return cnt;
}
void bfs(){
    while(!q.empty()){
        node fr = q.front();
        if(ok(fr)){
            cout << fr.t << endl;
            if(fr.t != 0)cout << fr.s << endl;
            return;
        }
        fr.t++;
        node en = fr;
        swap(en.a[1][1],en.a[2][1]);
        swap(en.a[1][2],en.a[2][2]);
        swap(en.a[1][3],en.a[2][3]);
        swap(en.a[1][4],en.a[2][4]);
        en.s += "A";
        if(!_m[get(en)]){q.push(en);_m[get(en)] = true;}
        //
        en = fr;
        swap(en.a[1][4],en.a[1][3]);
        swap(en.a[1][3],en.a[1][2]);
        swap(en.a[1][2],en.a[1][1]);
        swap(en.a[2][4],en.a[2][3]);
        swap(en.a[2][3],en.a[2][2]);
        swap(en.a[2][2],en.a[2][1]);
        en.s += "B";
        if(!_m[get(en)]){q.push(en);_m[get(en)] = true;}
        //
        en = fr;
        swap(en.a[2][2],en.a[2][3]);
        swap(en.a[2][3],en.a[1][3]);
        swap(en.a[1][3],en.a[1][2]);
        en.s += "C";
        if(!_m[get(en)]){q.push(en);_m[get(en)] = true;}
        q.pop();
    }
}
int main() {
    cin >> tar[1][1] >> tar[1][2] >> tar[1][3] >> tar[1][4];
    cin >> tar[2][4] >> tar[2][3] >> tar[2][2] >> tar[2][1];
    n0.a[1][1] = 1;n0.a[1][2] = 2;n0.a[1][3] = 3;n0.a[1][4] = 4;
    n0.a[2][1] = 8;n0.a[2][2] = 7;n0.a[2][3] = 6;n0.a[2][4] = 5;
    q.push(n0);
    bfs();
    return 0;
}


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

有猷
24天前
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define re register
#define Re register
#define MAXN 1005
int n,m,vis[MAXN][MAXN];
int dx[5] = {0,0,1,-1};
int dy[5] = {1,-1,0,0};
struct node{
    int x,y,t;
};
queue<node>q;
int main() {
    scanf("%d%d",&n,&m);
    memset(vis,-1,sizeof vis);
    for(re int i = 1;i <= n;i++){
        for(re int j = 1;j <= m;j++){
            int b;
            scanf("%1d",&b);
            if(b){
                q.push((node){i,j,0});
                vis[i][j] = 0;
            }
        }
    }
    //bfs
    while(!q.empty()){
        node fr = q.front();
        for(re int i = 0;i < 4;i++){
            int nx = fr.x + dx[i],ny = fr.y + dy[i];
            if(nx < 1 || ny < 1 || nx > n || ny > m || vis[nx][ny] != -1)continue;
            vis[nx][ny] = fr.t + 1;
            q.push((node){nx,ny,fr.t + 1});
        }
        q.pop();
    }
    for(re int i = 1;i <= n;i++){
        for(re int j = 1;j <= m;j++){
            cout << vis[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}


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

有猷
26天前
#include<iostream>
#include<queue>
using namespace std;
#define re register
#define Re register
#define MAXN 100005
struct node{
    int pos,t;
};
int n,k;
bool vis[MAXN * 2];
queue<node>q;
void bfs(){
    q.push((node){n,0});
    vis[n] = true;
    while(!q.empty()){
        node fr = q.front();
        if(fr.pos == k){
            cout << fr.t << endl;
            return;
        }
        if(fr.pos < k && !vis[fr.pos + 1]){q.push((node){fr.pos + 1,fr.t + 1});vis[fr.pos + 1] = true;}
        if(fr.pos - 1 > 0 && !vis[fr.pos - 1]){q.push((node){fr.pos - 1,fr.t + 1});vis[fr.pos - 1] = true;}
        if(fr.pos < k && !vis[fr.pos * 2]){q.push((node){fr.pos * 2,fr.t + 1});vis[fr.pos * 2] = true;}
        q.pop();
    }
}
int main() {
    cin >> n >> k;
    bfs();
    return 0;
}


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

有猷
1个月前

矩阵大小 $m,n$ 读入的坑人是蒟蒻无法想象的~

#include<iostream>
#include<queue>
using namespace std;
#define re register
#define Re register
#define MAXN 155
struct node{
    int x,y,t;
};
queue<node>q;
int n,m,stx,sty,enx,eny;
int dx[10] = {2,-2,2,-2,1,-1,-1,1};
int dy[10] = {1,-1,-1,1,2,-2,2,-2};
bool a[MAXN][MAXN];
void bfs(){
    q.push((node){stx,sty,0});
    a[stx][sty] = true;
    while(!q.empty()){
        node fr = q.front();
        if(fr.x == enx && fr.y == eny){
            cout << fr.t << endl;
            return;
        }
        for(re int i = 0;i < 8;i++){
            int nx = fr.x + dx[i],ny = fr.y + dy[i];
            if(nx < 1 || ny < 1 || nx > n || ny > m || a[nx][ny])continue;
            a[nx][ny] = true;
            q.push((node){nx,ny,fr.t + 1});
        }
        q.pop();
    }
}
int main(){
    cin >> m >> n;
    for(re int i = 1;i <= n;i++){
        for(re int j = 1;j <= m;j++){
            char ch;
            cin >> ch;
            if(ch == 'K'){
                stx = i;
                sty = j;
            }
            if(ch == 'H'){
                enx = i;
                eny = j;
            }
            if(ch == '*')a[i][j] = true;
        }
    }
    bfs();
    return 0;
}


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

有猷
1个月前
#include<iostream>
#include<queue>
using namespace std;
#define re register
#define Re register
#define MAXN 1005
struct node{
    int x,y;
};
queue<node> q;
int n,lx[MAXN][MAXN],ly[MAXN][MAXN];
int dx[5] = {1,-1,0,0};
int dy[5] = {0,0,1,-1};
bool a[MAXN][MAXN];
void bfs(){
    q.push((node){n,n});
    a[n][n] = true;
    while(!q.empty()){
        node fr = q.front();
        if(fr.x == 1 && fr.y == 1)return;
        for(re int i = 0;i < 4;i++){
            int nx = fr.x + dx[i],ny = fr.y + dy[i];
            if(nx < 1 || ny < 1 || nx > n || ny > n || a[nx][ny])continue;
            a[nx][ny] = true;
            lx[nx][ny] = fr.x;
            ly[nx][ny] = fr.y;
            q.push((node){nx,ny});
        }
        q.pop();
    }
}
int main() {
    cin >> n;
    for(Re int i = 1;i <= n;i++){
        for(re int j = 1;j <= n;j++){
            cin >> a[i][j];
        }
    }
    bfs();
    for(Re int x = 1,y = 1;x != n || y != n;){
        cout << x - 1 << ' ' << y - 1 << endl;
        int t = x;
        x = lx[x][y];y = ly[t][y];
    }
    cout << n - 1 << ' ' << n - 1 << endl;
    return 0;
}


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

有猷
1个月前

期中考试爆零祭~~~

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define re register
#define Re register
#define MAXN 1005
struct node{
    int x,y;
};
queue<node> q;
int n,mt,vl,idx,a[MAXN][MAXN],vis[MAXN][MAXN];
int dx[10] = {0,0,1,-1,1,-1,1,-1};
int dy[10] = {1,-1,0,0,-1,-1,1,1};
bool bfs1(int xi,int yi){
    while(!q.empty())
        q.pop();
    vis[xi][yi] = idx;
    q.push((node){xi,yi});
    while(!q.empty()){
        node fr = q.front();
        for(Re int i = 0;i < 8;i++){
            int nx = fr.x + dx[i],ny = fr.y + dy[i];
            if(nx < 1 || ny < 1 || nx > n || ny > n || a[nx][ny] < a[fr.x][fr.y])continue;
            if(a[nx][ny] > a[fr.x][fr.y] || a[nx][ny] == a[fr.x][fr.y] && (vis[nx][ny] != idx && vis[nx][ny] != 0))return false;
            if(vis[nx][ny] == 0){q.push((node){nx,ny});vis[nx][ny] = idx;}
        }
        q.pop();
    }
    return true;
}
bool bfs2(int xi,int yi){
    while(!q.empty())
        q.pop();
    vis[xi][yi] = idx;
    q.push((node){xi,yi});
    while(!q.empty()){
        node fr = q.front();
        for(Re int i = 0;i < 8;i++){
            int nx = fr.x + dx[i],ny = fr.y + dy[i];
            if(nx < 1 || ny < 1 || nx > n || ny > n || a[nx][ny] > a[fr.x][fr.y])continue;
            if(a[nx][ny] < a[fr.x][fr.y] || a[nx][ny] == a[fr.x][fr.y] && (vis[nx][ny] != idx && vis[nx][ny] != 0))return false;
            if(vis[nx][ny] == 0){q.push((node){nx,ny});vis[nx][ny] = idx;}
        }
        q.pop();
    }
    return true;
}
int main() {
    cin >> n;
    for(re int i = 1;i <= n;i++){
        for(Re int j = 1;j <= n;j++) {
            cin >> a[i][j];
        }
    }
    for(re int i = 1;i <= n;i++){
        for(re int j = 1;j <= n;j++){
            idx++;
            if(!vis[i][j])mt += bfs1(i,j);
        }
    }
    idx = 0;
    memset(vis,0,sizeof vis);
    for(re int i = 1;i <= n;i++){
        for(re int j = 1;j <= n;j++){
            idx++;
            if(!vis[i][j])vl += bfs2(i,j);
        }
    }
    cout << mt << ' ' << vl << endl;
    return 0;
}