头像

过眼云烟1


访客:17308

离线:1个月前


活动打卡代码 AcWing 1116. 马走日

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 10;

int m,n;
bool st[N][N];
int ans;
int dx[8] = {-2,-1,1,2,2,1,-1,-2};
int dy[8] = {1,2,2,1,-1,-2,-2,-1};
// int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
// int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};


void dfs(int x,int y,int cnt){
    if(cnt == m*n) {
        ans++;
        return;
    }
    st[x][y]=true;
    for(int i=0;i<8;i++){
        int a = x+dx[i],b=y+dy[i];
        if(a<0||a>=n||b<0||b>=m) continue;
        if(st[a][b]) continue;
        dfs(a,b,cnt+1);
    }
    st[x][y]=false;
}



int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int x,y;
        scanf("%d%d%d%d",&n,&m,&x,&y);

        memset(st,0,sizeof st);
        ans = 0;
        dfs(x,y,1);
        printf("%d\n",ans);
    }

    return 0;
}




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

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 25;

char g[N][N];
bool st[N][N];
int n,m;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
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(a<0||a>=n||b<0||b>=m) continue;
        if(g[a][b]!='.') continue;
        if(st[a][b]) continue;
        cnt+=dfs(a,b);
    }
    return cnt;
}

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


活动打卡代码 AcWing 1112. 迷宫

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110;

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

bool dfs(int x,int y){
    if (g[x][y] == '#') return false;
    if(x==xb&&y==yb) return true;
    st[x][y]=true;
    for(int i=0;i<4;i++){
        int a = x+dx[i],b=y+dy[i];
        if (a < 0 || a >= n || b < 0 || b >= n) continue;
        if (st[a][b]) continue;
        if (dfs(a, b)) return true;
    }
    return false;
}
bool sfs(int x, int y)
{
    if (g[x][y] == '#') return false;
    if (x == xb && y == yb) return true;

    st[x][y] = true;

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

    return false;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%s",g[i]);
        scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
        memset(st,0,sizeof st);
        if(dfs(xa,ya)) puts("YES");
        else puts("NO");
    }
    return 0;
}


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

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_map>

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[])
{
    auto 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]) continue;
            string r = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
            if (db.count(r)) return db[r] + da[t];
            if (da.count(r)) continue;

            da[r] = da[t] + 1;
            q.push(r);
        }

    return -1;
}



int bfs(string A, string B)
{
    queue<string> qa, qb;
    unordered_map<string, int> da, db;

    qa.push(A), da[A] = 0;
    qb.push(B), db[B] = 1;

    while (qa.size() && qb.size())
    {
        if (da[qa.front()] + db[qb.front()] > 10) return 11;

        int t;
        if (qa.size() <= qb.size()) t = extend(qa, da, db, a, b);
        else t = extend(qb, db, da, b, a);

        if (t != -1) return t;
    }

    return 11;
}



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


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

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
#include<cstring>
#include<deque>

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

const int N = 510,M=N*N;

int n,m;
char g[N][N];
int dist[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});
    char cs[] = "\\/\\/";
    int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
    int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
    while (q.size())
    {
        PII t = q.front();
        q.pop_front();

        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 || a > n || b < 0 || b > m) continue;

            int ca = t.x + ix[i], cb = t.y + iy[i];
            int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);

            if (d < dist[a][b])
            {
                dist[a][b] = d;

                if (g[ca][cb] != cs[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]);
        int t = bfs();
        if (t == 0x3f3f3f3f) puts("NO SOLUTION");
        else printf("%d\n", t);
    }
    return 0;
}


活动打卡代码 AcWing 1107. 魔板

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<queue>

using namespace std;
char g[2][4];
unordered_map<string,pair<char,string>> pre;
unordered_map<string,int> dist;

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

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 move0(string state)
{
    set(state);
    for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]);
    return get();
}

string move1(string state)
{
    set(state);
    int v0 = g[0][3], v1 = g[1][3];
    for (int i = 3; i >= 0; i -- )
    {
        g[0][i] = g[0][i - 1];
        g[1][i] = g[1][i - 1];
    }
    g[0][0] = v0, g[1][0] = v1;
    return get();
}

string move2(string state)
{
    set(state);
    int v = g[0][1];
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = v;
    return get();
}


int bfs(string start,string end)
{
    if(start == end) return 0;
    queue<string> q;
    q.push(start);
    dist[start] =0;

    while(!q.empty())
    {
        auto 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<3;i++){
            if(!dist.count(m[i]))
            {
                dist[m[i]] = dist[t] +1;
                pre[m[i]] ={'A'+i,t};
                q.push(m[i]);
                if(m[i]==end) return dist[end];
            }
        }
    }
    return -1;
}
int main()
{
    int x;
    string start,end;
    for(int i=0;i<8;i++)
    {
        cin>>x;
        end+=char(x+'0');
    }
    for(int i=1;i<=8;i++) start+=char('0'+i);

    int step = bfs(start,end);
    cout<<step<<endl;

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

    reverse(res.begin(),res.end());
    if(step > 0) cout<<res<<endl;
    return 0;
}


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

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 1010,M=N*N;

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


void bfs()
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    memset(dist, -1, sizeof dist);

    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (g[i][j] == '1')
            {
                dist[i][j] = 0;
                q[ ++ tt] = {i, j};
            }

    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 < 1 || a > n || b < 1 || b > m) continue;
            if (dist[a][b] != -1) continue;

            dist[a][b] = dist[t.x][t.y] + 1;
            q[ ++ tt] = {a, b};
        }
    }
}


int main(){
    scanf("%d %d",&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]);
        puts("");
    }
    return 0;
}


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

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 1010,M=N*N;

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


void bfs()
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    memset(dist, -1, sizeof dist);

    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (g[i][j] == '1')
            {
                dist[i][j] = 0;
                q[ ++ tt] = {i, j};
            }

    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 < 1 || a > n || b < 1 || b > m) continue;
            if (dist[a][b] != -1) continue;

            dist[a][b] = dist[t.x][t.y] + 1;
            q[ ++ tt] = {a, b};
        }
    }
}


int main(){
    scanf("%d %d",&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]);
        puts("");
    }
    return 0;
}


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

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10;

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

int bfs(){
    memset(dist,-1,sizeof dist);
    dist[n]=0;
    q[0]=n;
    int hh=0,tt=0;
    while(hh<=tt){
        int t= q[hh++];
        if(t==k) return dist[k];
        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 -1;
}
int main(){
    cin>>n>>k;
    cout<<bfs()<<endl;
    return 0;
}


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

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
#include<cstring>

#define x first
#define y second

using namespace std;
typedef pair<int,int> PII;

const int N = 155,M = N*N;
int n,m;
char g[N][N];
PII q[M];
int dist[N][N];
int bfs(){
    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    int sx,sy;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]=='K')
                sx=i,sy=j;
    int hh=0,tt=0;
    q[0]={sx,sy};
    memset(dist,-1,sizeof dist);
    dist[sx][sy]=0;
    while(hh<=tt){
        auto t = q[hh++];

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