头像

minux

SUFE


访客:5866

离线:10小时前



minux
16小时前

c++ dfs回溯

#include <bits/stdc++.h>
using namespace std;

const int N=15;
int n, m, sx, sy, t;
bool vis[N][N];
int ans, cnt;
const int dirs[8][2]={{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

void dfs(int x, int y){
    vis[x][y]=true;
    if(cnt==n*m) ans++;
    for(int i=0; i<8; ++i){
        int nx=x+dirs[i][0];
        int ny=y+dirs[i][1];
        if(0<=nx && nx<n && 0<=ny && ny<m && !vis[nx][ny]){
            cnt++;
            dfs(nx, ny);
            vis[nx][ny]=false;
            --cnt;
        }
    }
}


int main(){
    cin>>t;
    while(t--){
        cin>>n>>m>>sx>>sy;
        ans=0;
        memset(vis, 0x00, sizeof vis);
        cnt=1;
        dfs(sx, sy);
        cout<<ans<<endl;
    }

    return 0;
}


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

minux
16小时前
#include <bits/stdc++.h>
using namespace std;

const int N=15;
int n, m, sx, sy, t;
bool vis[N][N];
int ans, cnt;
const int dirs[8][2]={{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

void dfs(int x, int y){
    vis[x][y]=true;
    if(cnt==n*m) ans++;
    for(int i=0; i<8; ++i){
        int nx=x+dirs[i][0];
        int ny=y+dirs[i][1];
        if(0<=nx && nx<n && 0<=ny && ny<m && !vis[nx][ny]){
            cnt++;
            dfs(nx, ny);
            vis[nx][ny]=false;
            --cnt;
        }
    }
}


int main(){
    cin>>t;
    while(t--){
        cin>>n>>m>>sx>>sy;
        ans=0;
        memset(vis, 0x00, sizeof vis);
        cnt=1;
        dfs(sx, sy);
        cout<<ans<<endl;
    }

    return 0;
}


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

minux
1天前
#include <bits/stdc++.h>
using namespace std;

const int N=25;
char G[N][N];
bool vis[N][N];
int n, m;
int ans=0;
const int dirs[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void dfs(int x, int y){
    vis[x][y]=true;
    for(int i=0; i<4; ++i){
        int nx=x+dirs[i][0];
        int ny=y+dirs[i][1];
        if(0<=nx && nx<n && 0<=ny && ny<m && !vis[nx][ny] && G[nx][ny]=='.'){
            ++ans;
            dfs(nx, ny);
        }
    }
}

int main(){
    while(cin>>m>>n, m||n){
        memset(G, 0x00, sizeof G);
        memset(vis, 0x00, sizeof vis);
        for(int i=0; i<n; ++i) cin>>G[i];
        ans=1;
        for(int i=0; i<n; ++i){
            for(int j=0; j<m; ++j)
                if(G[i][j]=='@'){
                    dfs(i, j);
                    cout<<ans<<endl;
                    break;
                }
        }

    }


    return 0;
}



minux
1天前

python dfs

from typing import List
class Solution:
    def main(self, sx:int, sy:int, ex:int, ey:int, n: int, G:List[List[int]]):
        dirs=[[-1, 0], [0, 1], [1, 0], [0, -1]]
        vis = [[False for _ in range(n)] for _ in range(n)]
        def dfs(x, y):
            if G[x][y]=='#': return False
            if x==ex and y==ey: return True
            vis[x][y]=True
            for d in dirs:
                nx, ny = x+d[0], y+d[1]
                if 0<=nx and nx<n and 0<=ny and ny<n and not vis[nx][ny] and G[nx][ny]=='.':
                    if dfs(nx, ny): return True
            return False
        if dfs(sx, sy): print("YES")
        else: print("NO")



if __name__ == '__main__':
    T=int(input())
    sol=Solution()
    for _ in range(T):
        n=int(input())
        G=[[] for _ in range(n)]
        for i in range(n):
            G[i]=list(map(str, input()))
        sx, sy, ex, ey = map(int, input().split())
        sol.main(sx, sy, ex, ey, n, G)

c++ dfs

#include <bits/stdc++.h>
using namespace std;

const int N=105;

int n, T;
char G[N][N];
bool vis[N][N];
const int dirs[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int xa, ya, xb, yb;

bool dfs(int x, int y){
    if(G[x][y]=='#') return false;
    if(x==xb && y==yb) return true;
    vis[x][y]=true;
    for(int i=0; i<4; ++i){
        int nx=x+dirs[i][0];
        int ny=y+dirs[i][1];
        if(0<=nx && nx<n && 0<=ny &&ny<n && !vis[nx][ny] && G[nx][ny]=='.'){
            if(dfs(nx, ny)) return true;
        } 
    }
    return false;
}


int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=0; i<n; ++i) cin>>G[i];
        memset(vis, 0x00, sizeof vis);
        cin>>xa>>ya>>xb>>yb;
        if(dfs(xa, ya)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 1112. 迷宫

minux
1天前
#include <bits/stdc++.h>
using namespace std;

const int N=105;

int n, T;
char G[N][N];
bool vis[N][N];
const int dirs[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int xa, ya, xb, yb;

bool dfs(int x, int y){
    if(G[x][y]=='#') return false;
    if(x==xb && y==yb) return true;
    vis[x][y]=true;
    for(int i=0; i<4; ++i){
        int nx=x+dirs[i][0];
        int ny=y+dirs[i][1];
        if(0<=nx && nx<n && 0<=ny &&ny<n && !vis[nx][ny] && G[nx][ny]=='.'){
            if(dfs(nx, ny)) return true;
        } 
    }
    return false;
}


int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=0; i<n; ++i) cin>>G[i];
        memset(vis, 0x00, sizeof vis);
        cin>>xa>>ya>>xb>>yb;
        if(dfs(xa, ya)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

    return 0;
}


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

minux
1天前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 1010, M = 200010;

int n, m, S, T, K;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int dist[N];
int st[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 dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, T});

    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.y;
        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()
{
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({dist[S], {0, S}});

    memset(st, 0, sizeof st);

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.y.y, distance = t.y.x;
        st[ver] ++ ;

        if (ver == T && st[ver] == 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()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);

    for (int i = 0; i < m; i ++ )
    {
        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 ++ ;

    dijkstra();
    printf("%d\n", astar());

    return 0;
}



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

minux
2天前
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, string> PIS; // 估计距离-状态
#define x first
#define y second

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(string start){
    // A*估价函数f(x)=g(x)+h(x)
    // g(x)表示x到初始状态的距离
    // h(x)为启发式函数, 表示x到目标状态的距离, 本题中使用曼哈顿距离作为启发式函数
    unordered_map<string, int> dist; 
    unordered_map<string, pair<char, string>> prev; // 记录上一个操作及状态
    priority_queue<PIS, vector<PIS>, greater<PIS>> heap; // 使用小根堆作为A*的容器
    int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1}; // 定义方向数组
    char *op="urdl";
    string end="12345678x";

    dist[start]=0;
    heap.push({f(start), start}); // <估价函数-状态>入队列
    while(!heap.empty()){
        auto t=heap.top();
        heap.pop();
        string state=t.y;
        if(state==end) break;
        int x, y;
        for(int i=0; i<9; ++i)
            if(state[i]=='x'){
                x=i/3;
                y=i%3;
                break;
            }
        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;
            state=source; // 恢复现场
            swap(state[x*3+y], state[a*3+b]);
            if(dist.count(state)==0 || dist[state]>dist[source]+1){
                dist[state]=dist[source]+1;
                prev[state]={op[i], source};
                heap.push({dist[state]+f(state), state});
            }
        }

    }
    // 逆向推导路径
    string res;
    while(end!=start){
        res+=prev[end].x;
        end=prev[end].y;
    }
    reverse(res.begin(), res.end());
    return res;

}

int main(){
    string start, seq;
    char c;
    while(cin>>c){
        start+=c;
        if(c!='x') seq+=c;
    }

    // 计算逆序对的数量
    int cnt=0;
    for(int i=0; i<8; ++i)
        for(int j=i; j<8; ++j)
            if(seq[i]>seq[j])
                cnt++;
    if(cnt&0x01) puts("unsolvable");
    else cout<<bfs(start)<<endl;


    return 0;
}


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

minux
5天前
#include <bits/stdc++.h>
using namespace std;

const int N=6;
string a[N], b[N];
int n=0;

int ext(queue<string> &q, unordered_map<string, int> &da, unordered_map<string, int> &db, string a[], string b[]){
    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 state=t.substr(0, i)+b[j]+t.substr(i+a[j].size());
                if(db.count(state)) return da[t]+1+db[state];
                if(da.count(state)) continue;
                da[state]=da[t]+1;
                q.push(state);
            }
    return 11;
}


int main(){
    string A, B;
    cin>>A>>B; // 读取字符串
    while(cin>>a[n]>>b[n]) n++;

    // 双向bfs搜索
    function <int(string, string)> bfs=[&](string A, string B){
        queue<string> qa, qb;
        unordered_map<string, int> da, db;
        da[A]=0;
        db[B]=0;
        qa.push(A);
        qb.push(B);
        while(!qa.empty() && !qb.empty()){
            int t;
            if(qa.size()<=qb.size()) t=ext(qa, da, db, a, b);
            else t=ext(qb, db, da, b, a);
            if(t<=10) return t;
        }
        return 11;
    };

    int step=bfs(A, B);
    if(step>10) puts("NO ANSWER!");
    else cout<<step<<endl;

    return 0;
}


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

minux
6天前
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
#define fi first
#define se second

const int N=505;
int n, m, t;
char G[N][N];
int dist[N][N];
bool vis[N][N];
const int dirs[4][2]={{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
const int offset[4][2]={{-1, -1}, {-1, 0}, {0, 0}, {0, -1}};
const char cs[5]="\\/\\/";

int main(){
    function<int(int, int)> bfs=[&](int posx, int posy){
        deque<PII> q;
        q.push_back({posx, posy});
        dist[posx][posy]=0;
        while(!q.empty()){
            int x=q.front().fi;
            int y=q.front().se;
            q.pop_front();
            if(x==n && y==m) return dist[x][y];
            if(vis[x][y]) continue;
            vis[x][y]=true;
            for(int i=0; i<4; ++i){
                int nx=x+dirs[i][0];
                int ny=y+dirs[i][1];
                if(nx<0 || nx>n || ny<0 || ny>m) continue;
                int gx=x+offset[i][0], gy=y+offset[i][1];
                int w=(G[gx][gy]!=cs[i]);
                int d=dist[x][y]+w;
                if(d<=dist[nx][ny]){
                    dist[nx][ny]=d;
                    if(!w) q.push_front({nx, ny});
                    else q.push_back({nx, ny});
                }
            }
        }
        return -1;
    };

    cin>>t;
    while(t--){
        memset(dist, 0x3f, sizeof dist);
        memset(G, 0x00, sizeof G);
        memset(vis, 0x00, sizeof vis);
        cin>>n>>m;
        for(int i=0; i<n; ++i) cin>>G[i];
        if((n+m)&0x01) puts("NO SOLUTION");
        else cout<<bfs(0, 0)<<endl;
    }

    return 0;
}



minux
6天前
#include <bits/stdc++.h>
using namespace std;

typedef pair<char, string> PCS;
#define fi first
#define se second

char G[2][4];
unordered_map<string, int> dist;
unordered_map<string, PCS> pre;

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

void _set(string state){
    for(int i=0; i<4; ++i) G[0][i]=state[i];
    for(int i=3, j=4; i>=0; --i, ++j) G[1][i]=state[j];
}


int main(){
    char x;
    string start, end;
    for(int i=0; i<8; ++i){cin>>x; end+=x;} // 存储目标状态
    for(int i=0; i<8; ++i) start+=i+'1'; // 存储起始状态

    function<string(string)> move0=[&](string st){ // A:交换上下两行
        _set(st);
        for(int i=0; i<4; ++i) swap(G[0][i], G[1][i]);
        return _get();
    };

    function<string(string)> move1=[&](string st){ // B:最右列插入到最左侧
        _set(st);
        char e0=G[0][3], e1=G[1][3];
        for(int i=3; i>0; --i)
            for(int j=0; j<2; ++j)
                G[j][i]=G[j][i-1];

        G[0][0]=e0;
        G[1][0]=e1;
        return _get();
    };

    function<string(string)> move2=[&](string st){ // C:中间4个数进行顺时针旋转
        _set(st);
        char e=G[0][1];
        G[0][1]=G[1][1];
        G[1][1]=G[1][2];
        G[1][2]=G[0][2];
        G[0][2]=e;
        return _get();
    };

    function<void(string, string)> bfs=[&](string start, string end){
        if(start==end) return;
        queue<string> q;
        q.push(start);
        dist[start]=0;
        while(!q.empty()){
            auto t=q.front();
            q.pop();
            string move[3];
            move[0]=move0(t);
            move[1]=move1(t);
            move[2]=move2(t);

            for(int i=0; i<3; ++i){
                string m=move[i];
                if(dist.count(m)==0){
                    dist[m]=dist[t]+1;
                    pre[m]={char(i+'A'), t};
                    if(m==end) break;
                    q.push(m);
                }
            }
        }
    };

    bfs(start, end);
    cout<<dist[end]<<endl;

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

    reverse(res.begin(), res.end());
    if(res.size()) cout<<res<<endl;

    return 0;
}