堕人間の備忘録

フナチーズ・ドロップアウト

幅優先探索？！

広義昨日解いたチーズについてです

初めて幅優先探索書きました

もちろんあり本に頼りつつ

せっかくなので自分のためにコード八説きます

にゃにゃにゃにゃ

typedef pair<int ,int> P;
char masu[1003][1003];
int W,H,K,ans=0;
int sx[10],sy[10];
int gx[10],gy[10];
 
int d[1003][1003];
 
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
 
queue<P> que;
 
void sho(){
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            d[j][i]=INF;
        }
    }
    while(que.size()){
        que.pop();
    }
}
 
int bfs(){
    for(int i=0;i<K;i++){
        sho();
        que.push(P(sx[i],sy[i]));
        d[sx[i]][sy[i]]=0;
        while(que.size()){
            P p=que.front();que.pop();
            if(p.first==gx[i+1]&&p.second==gy[i+1])break;
            for(int j=0;j<4;j++){
                int nx = p.first+dx[j],ny = p.second+dy[j];
                if(0<=nx&nx<W&&0<=ny&&ny<H&&masu[nx][ny]!='X'&&d[nx][ny]==INF){
                    que.push(P(nx,ny));
                    d[nx][ny] = d[p.first][p.second] + 1;
                }
            }
        }ans+=d[gx[i+1]][gy[i+1]];
    }
    return ans;
}
 
signed main(){
    cin >> H >> W >> K;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> masu[j][i];
            int a=masu[j][i]-'0';
            if(isdigit(masu[j][i])){
                gx[a]=j,gy[a]=i,sx[a]=j,sy[a]=i;
            }else if(masu[j][i]=='S'){
                sx[0]=j,sy[0]=i;
            }
        }
    }
    int answer = bfs();
    cout << answer << endl;
return 0;
}

小鳥が泣いたよほけきょ?

 

ーーーーーーー❀おまけ❀ーーーーーーーー

最初書いた、幅を知らず、つよしさん達に教えてもらう前のコード

貼っときます

#include<bits/stdc++.h>
#include<ctype.h>
#define int long long int
#define rep(a,b) for(int a=0;a<b;a++)
#define INF 1000006
using namespace std;
 
int tx[] = {1,0,-1,0};
int ty[] = {0,1,0,-1};
int w,h,che,sx,sy;
char bases;
int base[1003][1003],base2[1003][1003],memo[1003][1003];
 
int chee(int x,int y,int n){
    int ans=INF;
    if(memo[x][y]>0&&(memo[x][y]!=INF||base[x][y]<0))return memo[x][y];
    else if(base[x][y]==n)return 0;
    else if(base[x][y]>=0){
        base[x][y]=-1;
        for(int i=0;i<4;i++){
            if(x+tx[i]>=0&&x+tx[i]<w&&y+ty[i]>=0&&y+ty[i]<h){
                ans = min(ans,chee(x+tx[i],y+ty[i],n)+1);
            }
        }base[x][y]=0;
    }
    memo[x][y]=ans;
    return ans;
}
void sho(int b[1003][1003],int a[1003][1003]){
    rep(i,1003){
        rep(j,1003){
            b[i][j]=a[i][j];
        }
    }
}
 
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int zx[20],zy[20];
    cin >> h >> w >> che;
    rep(f,h){
        rep(s,w){
            cin >> bases;
            switch(bases){
                case 'S':sx=s;sy=f;
                case '.':base[s][f]=0;
                break;
                case 'X':base[s][f]=-1;
                break;
                default:{base[s][f]=bases - '0';
                        zx[base[s][f]]=s;
                        zy[base[s][f]]=f;
                        }
 
            }
        }
    }
    sho(base2,base);
    int ans=0;
    ans+=chee(sx,sy,1);
    for(int i=2;i<=che;i++){
        sho(base,base2);
        fill((int*)memo,(int*)(memo+1003),0);
        ans+=chee(zx[i-1],zy[i-1],i);
    }
    cout << ans << endl;
return 0;
}

 上のコードの感想は、「強引」ですね★★

 

ただ今の時刻4時半です良い子は寝ましょう。

 

補足::コメント何かしらあったらお願いです～★★