头像

十六




离线:5小时前



十六
5小时前
#include<bits/stdc++.h>
using namespace std;
const int N = 10;

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

int extend(queue<string> &q, unordered_map<string, int> &mp, unordered_map<string, int> &mq, string a[], string b[]){
    //将已经在队列中的字符串全部扩展一步
    for(int k=0, kk=q.size(); k<kk; k++){

        string str = q.front();
        q.pop();

        for(int i=0, ii=str.size(); i<ii; i++){
            for(int j=0; j<n; j++){

                if(str.substr(i, a[j].size())==a[j]){
                    string nstr = str.substr(0, i) + b[j] + str.substr(i+a[j].size());

                    if(mq.count(nstr)) return mp[str] + mq[nstr] + 1; //在另一个队列中存在,两个方向有交集

                    if(mp.count(nstr)) continue; //扩展的字符串已经出现过

                    q.push(nstr);
                    mp[nstr] = mp[str]+1;
                }
            }
        }
    }

    return 11;
}

int bfs(){
    queue<string> qa, qb;
    unordered_map<string, int> va, vb;

    qa.push(sa), qb.push(sb);
    va[sa] = 0, vb[sb] = 0;

    //两个队列有一个为空时,就是不可达的
    while(qa.size() && qb.size()){

        int res;

        //优先搜索较短的队列
        if(qa.size()<=qb.size()) res = extend(qa, va, vb, a, b);
        else res = extend(qb, vb, va, b, a);

        if(res<=10) return res;
    }

    return 11;
}

int main(){
    cin>> sa>> sb;
    while(cin>> a[n]>> b[n]) n++;

    int ans = bfs();
    if(ans>10) puts("NO ANSWER!");
    else printf("%d\n", ans);

    return 0;
}



十六
2天前
#include<bits/stdc++.h>
using namespace std;
const int MAX = 5e2+10;
typedef pair<int, int> PII;

int r, c, t;
char g[MAX][MAX];
int dis[MAX][MAX];
deque<PII> dq;
int da[4][2] = {-1, -1, -1, 1, 1, 1, 1, -1}; //可以走的四个方向
int db[4][2] = {-1, -1, -1, 0, 0, 0, 0, -1}; //四个方向的元件的位置
char dc[4] = {'\\', '/', '\\', '/'};         //四个方向上不需要旋转元件情况下 应该有的元件形式

int bfs(){
    memset(dis, 0x3f, sizeof dis);
    dq.push_front({0, 0});
    dis[0][0] = 0;

    /**
     * 从一个点到另一个点,
     * 如果不需要旋转元件,视为这条路径的权值为0
     * 如果需要旋转元件,视为这条路的权值为1
     * 所以从一个点到另一个点的一条路可能有不同的权值
     * 也就是说,经过一个元件有两条不同方向的路(↘和↗)
     * 所以经过这个元件的最短距离有可能被更小的值覆盖(dijkstra)
     * 所以需要到最后出队才能确定最小的旋转次数
     * 
     * 本题中双端队列存放时:不需要旋转插入队头,需要旋转插入队尾
     **/

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

        for(int i=0; i<4; i++){
            int x = t.first, y = t.second;
            int xx = x+da[i][0], yy = y+da[i][1];

            if(xx<0 || xx>r || yy<0 || yy>c) continue; //格点是r+1行,c+1列

            int bx = x+db[i][0], by = y+db[i][1];
            int w = (g[bx][by]!=dc[i]); //权值 需要旋转,视为路径权值为1

            if(dis[x][y]+w < dis[xx][yy]){
                dis[xx][yy] = dis[x][y]+w;

                if(w) dq.push_back({xx, yy});
                else dq.push_front({xx, yy});
            }
        } 
    }

    return dis[r][c];
}

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

    while(t--){
        scanf("%d%d", &r, &c);

        for(int i=0; i<r; i++) scanf("%s", g[i]);

        //横纵坐标和为奇数的点一定不能到达,可以画图看看哪些点能到达,哪些不能到达,找一下规律
        if(r+c & 1) cout<< "NO SOLUTION"<< endl;
        else cout<< bfs()<< endl;
    }

    return 0;
}



十六
2天前
#include<bits/stdc++.h>
using namespace std;
typedef pair<string, pair<string, int>> PII; //魔板-步骤-次数

string a, b;
int t, g[10];
set<string> st;
queue<PII> q;

void setg(string t){
    for(int i=0; i<8; i++) g[i] = t[i]-'0';
}

string getg(){
    string t = "";
    for(int i=0; i<8; i++) t += g[i] + '0';
    return t;
}

PII opA(PII t){
    setg(t.first);

    for(int i=0; i<4; i++) swap(g[i], g[7-i]);

    return {getg(), {t.second.first+'A', t.second.second+1}};
}

PII opB(PII t){
    setg(t.first);

    for(int i=3; i>0; i--) swap(g[i], g[i-1]), swap(g[7-i], g[7-i+1]);

    return {getg(), {t.second.first+'B', t.second.second+1}};
}

PII opC(PII t){
    setg(t.first);

    int tmp = g[1];
    g[1] = g[6], g[6] = g[5], g[5] = g[2], g[2] = tmp;

    return {getg(), {t.second.first+'C', t.second.second+1}};
}

PII bfs(){
    q.push({a, {"", 0}});
    st.insert(a);

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

        PII nt[3];
        nt[0] = opA(t);
        nt[1] = opB(t);
        nt[2] = opC(t);

        for(int i=0; i<3; i++){
            if(nt[i].first==b) return nt[i];

            if(st.count(nt[i].first)) continue;

            st.insert(nt[i].first);
            q.push(nt[i]);
        }
    }

    return {"", {"", -1}};
}

int main(){
    a = "12345678";
    for(int i=0; i<8; i++){
        scanf("%d", &t);
        b += t+'0';
    }

    if(a==b) cout<< "0"<< endl; 
    else{
        PII ans = bfs();
        cout<< ans.second.second<< endl<< ans.second.first<< endl;
    }

    return 0;
}



十六
2天前
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 1e3+10;
typedef pair<int, int> PII;

int n, m;
char g[MAX][MAX];
int dis[MAX][MAX];
int d[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
queue<PII> q;

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

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(g[i][j]=='1') dis[i][j] = 0, q.push({i, j});
        }
    }

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

        for(int i=0; i<4; i++){
            int x = t.first+d[i][0], y = t.second+d[i][1];

            if(x<0 || x>=n || y<0 || y>=m) continue;
            if(dis[x][y]!=-1) continue;

            dis[x][y] = dis[t.first][t.second] + 1;
            q.push({x, y});
        }
    }

    return ;
}

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

    for(int i=0; i<n; i++) scanf("%s", g[i]);

    bfs();

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            printf("%d ", dis[i][j]);
        }
        printf("\n");
    }

    return 0;
}



十六
2天前
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5;
typedef pair<int, int> PII;

int x, y;
PII q[MAX*6];
bool v[MAX*2];

int bfs(int x){
    int hh = 0, tt = 0;
    q[hh] = {x, 0};

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

        //位置小于1e5时+1才有意义
        if(t.first<MAX){
            x = t.first+1;
            if(x==y) return t.second+1;
            else if(!v[x]) q[++tt] = {x, t.second+1}, v[x] = true;
        }

        //位置大于0时-1才有意义
        if(t.first>0){
            x = t.first-1;
            if(x==y) return t.second+1;
            else if(!v[x]) q[++tt] = {x, t.second+1}, v[x] = true;
        }

        //位置在(0, 1e5)范围内*2才有意义
        if(t.first>0 && t.first<MAX){
            x = t.first*2;
            if(x==y) return t.second+1;
            else if(!v[x]) q[++tt] = {x, t.second+1}, v[x] = true;
        }
    }

    return -1;
}

int main(){
    scanf("%d%d", &x, &y);

    cout<< bfs(x)<< endl;

    return 0;
}



十六
2天前
#include<bits/stdc++.h>
using namespace std;
const int MAX = 150+5;
typedef pair<int, int> PII;

int r, c;
char g[MAX][MAX];
int dis[MAX][MAX];
PII q[MAX*MAX];
int d[8][2] = {-2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, -2, -2, -1};

int bfs(int x, int y){
    int hh = 0, tt = 0;
    memset(dis, -1, sizeof dis);
    dis[x][y] = 0;
    q[hh] = {x, y};

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

        for(int i=0; i<8; i++){
            x = t.first+d[i][0], y = t.second+d[i][1];

            if(x<0 || x>=r || y<0 || y>=c) continue;
            if(dis[x][y]!=-1) continue;
            if(g[x][y]=='*') continue;

            dis[x][y] = dis[t.first][t.second] + 1;
            if(g[x][y]=='H') return dis[x][y];

            q[++tt] = {x, y};
        }
    }

    return -1;
}

int main(){
    scanf("%d%d", &c, &r);

    for(int i=0; i<r; i++) scanf("%s", g[i]);

    int x, y;
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            if(g[i][j]=='K'){
                x = i, y = j;
                break;
            }
        }
    }

    cout<< bfs(x, y)<< endl;

    return 0;
}



十六
2天前
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e3+10;
typedef pair<int, int> PII;

int n;
int g[MAX][MAX];
PII pre[MAX][MAX], q[MAX*MAX];
int d[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};

void bfs(int x, int y){
    memset(pre, -1, sizeof pre);
    int hh = 0, tt = 0;
    pre[x][y] = {0, 0};
    q[hh] = {x, y};

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

        for(int i=0; i<4; i++){
            x = t.first+d[i][0], y = t.second+d[i][1];

            if(x<0 || x>=n || y<0 || y>=n) continue;
            if(pre[x][y].first!=-1) continue;
            if(g[x][y]) continue;

            pre[x][y] = t;
            q[++tt] = {x, y};
        }
    }
}

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

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &g[i][j]);
        }
    }

    bfs(n-1, n-1);

    PII t(0, 0);
    while(1){
        printf("%d %d\n", t.first, t.second);
        if(t.first==n-1 && t.second==n-1) break;
        t = pre[t.first][t.second];
    }

    return 0;
}



十六
4天前
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e3+10;
typedef pair<int, int> PII;

int n, ansf, ansg;
int g[MAX][MAX];
bool v[MAX][MAX];
PII q[MAX*MAX];

void bfs(int r, int c, bool& hh, bool& hl){
    int h = 0, t = 0;
    q[h] = {r, c};
    v[r][c] = true;

    while(h<=t){
        PII tmp = q[h++];
        r = tmp.first, c = tmp.second;

        for(int i=-1; i<2; i++){
            for(int j=-1; j<2; j++){
                if(i==0 && j==0) continue;

                int rr = r + i, cc = c + j;
                if(rr<0 || rr>=n || cc<0 || cc>=n) continue;
                //if(rr<0 || rr>=n || cc<0 || cc>=n || v[rr][cc]) continue; 这是错的,因为后面要处理是不是山峰或山谷的问题

                if(g[r][c]==g[rr][cc] && !v[rr][cc]){
                    v[rr][cc] = true;
                    q[++t] = {rr, cc};
                }

                if(g[r][c]<g[rr][cc]) hh = true;
                if(g[r][c]>g[rr][cc]) hl = true;

            }
        }
    }
}

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

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &g[i][j]);
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!v[i][j]){
                bool hh = false, hl = false; //hh表示有比它高的位置 hl表示有比它低的位置
                bfs(i, j, hh, hl);

                if(!hl) ansg++;
                if(!hh) ansf++;
            }
        }
    }

    cout<< ansf<< " "<< ansg<< endl;

    return 0;
}



十六
4天前
#include<bits/stdc++.h>
using namespace std;
const int MAX = 50+5;
typedef pair<int, int> PII;

int n, m, num, mx;
int g[MAX][MAX];
bool v[MAX][MAX];
PII q[MAX*MAX];
int d[4][2] = {0, -1, -1, 0, 0, 1, 1, 0};

int bfs(int r, int c){
    int hh = 0, tt = 0, rs = 1;
    q[hh] = {r, c};
    v[r][c] = true;

    while(hh<=tt){
        PII t = q[hh++];
        r = t.first, c = t.second;

        for(int i=0; i<4; i++){
            if((g[r][c]>>i)&1) continue;

            int rr = r + d[i][0], cc = c + d[i][1];

            if(rr<0 || rr>=n || cc<0 || cc>=m || v[rr][cc]) continue;

            rs++;
            v[rr][cc] = true;
            q[++tt] = {rr, cc};
        }
    }

    return rs;
}

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

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &g[i][j]);
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(!v[i][j]){
                mx = max(mx, bfs(i, j));

                num++;
            }
        }
    }

    cout<< num<< endl<< mx<< endl;

    return 0;
}



十六
4天前
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e3+10;
typedef pair<int, int> PII;

int n, m;
int ans;
char g[MAX][MAX];
bool v[MAX][MAX];
PII q[MAX*MAX];

void bfs(int r, int c){
    int hh = 0, tt = 0;
    v[r][c] = true;
    q[0] = {r, c};

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

        for(int i=-1; i<2; i++){
            for(int j=-1; j<2; j++){
                if(i==0 && j==0) continue;

                int rr = t.first+i, cc = t.second+j;
                if(rr<0 || rr>=n || cc<0 || cc>=m) continue;
                if(g[rr][cc]=='.' || v[rr][cc]) continue;

                q[++tt] = {rr, cc};
                v[rr][cc] = true;
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    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(!v[i][j] && g[i][j]=='W'){
                bfs(i, j);
                ans++;
            }
        }
    }

    cout<< ans<< endl;

    return 0;
}