幅優先探索?!
広義昨日解いたチーズについてです
初めて幅優先探索書きました
もちろんあり本に頼りつつ
せっかくなので自分のためにコード八説きます
にゃにゃにゃにゃ
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時半です良い子は寝ましょう。
補足::コメント何かしらあったらお願いです~★★