bfs+最大連通成分(最大財宝数)、bfs+最短
5705 ワード
一、bfs+最短
タイトルリンク
題意翻訳
【題名説明】この問題は3次元の迷宮問題で、その中で‘.’空き地を表し、‘#’は障害物を表し、‘S’は起点を表し、‘E’は終点を表し、起点から終点までの最小移動回数を求める.上下左右前後に移動することができて、毎回すべて隣の空席まで移動することしかできなくて、毎回1分かかります.起点から終点まで最低どのくらいかかりますか.
【入力】複数組のテストデータ.
テストテストデータのセットは、3 D迷路を表します.
最初の3つの数は、それぞれ層数、1つの面の長さと幅を表し、後ろは各層の平面図である.最初の3つのデータは3つのゼロで終わりを表します.
【出力】最小移動回数.
Translated by@剣聖夜雨音烦
入出力サンプル
入力#13 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
出力#1コピーEscaped in 11 minute(s).
Trapped!
コード:stepの変化に注意(step保存最短長)# include
using namespace std;
int vis[32][32][32];
char Map[32][32][32];
struct node{
int x;
int y;
int z;
char value;
int step;
};
int dir[6][3]={
{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1} };
int main(){
int l,r,c;
while(cin>>l>>r>>c){
if(l==0&&r==0&&c==0)
return 0;
for(int i=1;i<=l;i++){
for(int j=1;j<=r;j++){
for(int k=1;k<=c;k++){
cin>>Map[i][j][k];
}
}
}
queueq;
for(int i=1;i<=l;i++){
for(int j=1;j<=r;j++){
for(int k=1;k<=c;k++){
if(Map[i][j][k]=='S'){
vis[i][j][k]=1;
q.push(node{i,j,k,'S'});
}
}
}
}
while(!q.empty()){
node v=q.front();
if(v.value=='E'){
cout<=1&&xx<=l&&yy>=1&&yy<=r&&zz>=1&&zz<=c&&vis[xx][yy][zz]==0&&(Map[xx][yy][zz]=='.'||Map[xx][yy][zz]=='E')){
vis[xx][yy][zz]=1;
next.step=v.step+1;
next.value=Map[xx][yy][zz];
q.push(next);
}
}
}
if(q.empty())
cout<
二、bfs+最大連通成分(一度に検索した最大財宝数)
タイトルリンク
J. Binbin's treasure map
説明
Binbin is a clever boy who likes to wear a skirt. One day,he saw some beautiful skirts on Taobao,but he had not enough money, which made him sad.
In order to make Binbin feel happy again, his's friend Xu1024 gave him atreasuremap. Thetreasure map is composed of three characters: '.', '#', '$'.
Character '.' indicates that this position is empty and passable;
Character '#' indicates that this position is blocked by a stone and not passable;
Character '$' indicates that this position has 1 coin on it and is passable.
The locations outside the treasure map are all empty and passable.
Binbin can move up, down, left, and right, but not at an angle.
Firstly, Binbin can choose any grid as starting point. Because Binbin wants to wear a skirt so much, he has a chance to teleport to a certain grid as another starting point.
Binbin wants to know how many coins he could eventually collect to buy skirts.
Can you help him?
入力
The first line of each group contains two numbers N and M(1<=N,M<=500),representing thenumber of rows and the number of columns of treasure map. Then there are next N lines, each line contains M characters. which describe the treasure map.
しゅつりょく
Ouput a integer representing the maxinum coin(s) Binbin would collect.
入力4 4
.$.$
.##.
#$#.
.#.#
しゅつりょく3
入力4 4
.#$#
####
..$$
$$$$
しゅつりょく7
$の2つの最大の連通成分を探して、和を求めればいいです.
acコード:# include
using namespace std;
struct node{
int x;
int y;
char z;
};
bool cmp(int a,int b){
return a>b;
}
int dir[4][2]={0,-1,-1,0,0,1,1,0};
int vis[510][510];
char Map[510][510];
int main(){
int n,m;
cin>>n>>m;
int sum[250006]={0};
int t=-1;
char s;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>s;
Map[i][j]=s;
}
}
for(int i=0;i<=n+1;i++){
if(i==0||i==n+1){
for(int j=0;j<=m+1;j++){
Map[i][j]='.';
}
}else{
Map[i][0]='.';
Map[i][m+1]='.';
}
}
// cout<
アリ雲建駅-企業にインターネットの「速い」サービスを提供2020年に突然の疫病のため、多くの企業が深刻な衝撃を受け、疫病の衝撃力は伝統的な「純線下」業界に最も危害を及ぼし、インターネットの女王マリー・ミック(MaryMeeker)は4月17日に有名な年度インターネットトレンド報告書を発表した.報告書は、強力なインターネット上のオンラインとオフラインの融合能力を持つ企業が疫病の中で最もよく表現され、オンラインとオフラインの融合傾向はすでにしばらく存在しているが、疫病はこのような需要をさらに切実にしていると指摘した.もしあなたの企業が伝統的な純粋なラインの下の経験モデルに完全に依存しているならば、2020年にあなたは「必ず死ぬ」ことになります.巨大で、かつてないインターネット革命が到来しました.アリ雲建駅は各業界の復工・復産を支援するため、疫病期間中に「馬がひっきりなしに足を踏み入れる」ことは数万人の企業のために迅速に駅を建設し、彼らのために「オンラインとオフラインの融合」あるいは「純オンライン」のインターネット経営モデルに向かって邁進し、堅固な基礎を築いた.「雲・速成美駅」テンプレートは1日でオンラインになり、技術が分からなくても大丈夫で、タイプすればサイトを作ることができます.千セットのウェブサイトのテンプレートは無料で提供して、100元は公式サイトを建てることができて、1価はすべて包んで、いかなる隠れた消費がありません."云・企业の公式サイト"のカスタマイズは1周间でオンラインになることができて、ハイエンドのカスタマイズは駅を建てて、千元の公式サイトは自分で手を出す必要はありませんて、駅の専门家の1対1のウェブサイトの企画と设计、専门の安心の选択.疫病は、大きな波が砂を洗うので、毎回の危機の背後にはチャンスが隠されていて、危機が大きいほど、チャンスも大きくなります.大きな環境はすでに変わっています.もしあなたがこの大きな環境に迎合するために努力しなければ、あなたは必ず淘汰されます.阿里云は企业の建设を助けて、优遇は多くて、福祉は多くて、详しくは以下のリンクをクリックしてくださいhttps://www.aliyun.com/minisite/goods?userCode=tz7kl4ag
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0Escaped in 11 minute(s).
Trapped!# include
using namespace std;
int vis[32][32][32];
char Map[32][32][32];
struct node{
int x;
int y;
int z;
char value;
int step;
};
int dir[6][3]={
{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1} };
int main(){
int l,r,c;
while(cin>>l>>r>>c){
if(l==0&&r==0&&c==0)
return 0;
for(int i=1;i<=l;i++){
for(int j=1;j<=r;j++){
for(int k=1;k<=c;k++){
cin>>Map[i][j][k];
}
}
}
queueq;
for(int i=1;i<=l;i++){
for(int j=1;j<=r;j++){
for(int k=1;k<=c;k++){
if(Map[i][j][k]=='S'){
vis[i][j][k]=1;
q.push(node{i,j,k,'S'});
}
}
}
}
while(!q.empty()){
node v=q.front();
if(v.value=='E'){
cout<=1&&xx<=l&&yy>=1&&yy<=r&&zz>=1&&zz<=c&&vis[xx][yy][zz]==0&&(Map[xx][yy][zz]=='.'||Map[xx][yy][zz]=='E')){
vis[xx][yy][zz]=1;
next.step=v.step+1;
next.value=Map[xx][yy][zz];
q.push(next);
}
}
}
if(q.empty())
cout< タイトルリンク
J. Binbin's treasure map
説明
Binbin is a clever boy who likes to wear a skirt. One day,he saw some beautiful skirts on Taobao,but he had not enough money, which made him sad.
In order to make Binbin feel happy again, his's friend Xu1024 gave him atreasuremap. Thetreasure map is composed of three characters: '.', '#', '$'.
Character '.' indicates that this position is empty and passable;
Character '#' indicates that this position is blocked by a stone and not passable;
Character '$' indicates that this position has 1 coin on it and is passable.
The locations outside the treasure map are all empty and passable.
Binbin can move up, down, left, and right, but not at an angle.
Firstly, Binbin can choose any grid as starting point. Because Binbin wants to wear a skirt so much, he has a chance to teleport to a certain grid as another starting point.
Binbin wants to know how many coins he could eventually collect to buy skirts.
Can you help him?
入力
The first line of each group contains two numbers N and M(1<=N,M<=500),representing thenumber of rows and the number of columns of treasure map. Then there are next N lines, each line contains M characters. which describe the treasure map.
しゅつりょく
Ouput a integer representing the maxinum coin(s) Binbin would collect.
入力4 4
.$.$
.##.
#$#.
.#.#
しゅつりょく3
入力4 4
.#$#
####
..$$
$$$$
しゅつりょく7
$の2つの最大の連通成分を探して、和を求めればいいです.
acコード:# include
using namespace std;
struct node{
int x;
int y;
char z;
};
bool cmp(int a,int b){
return a>b;
}
int dir[4][2]={0,-1,-1,0,0,1,1,0};
int vis[510][510];
char Map[510][510];
int main(){
int n,m;
cin>>n>>m;
int sum[250006]={0};
int t=-1;
char s;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>s;
Map[i][j]=s;
}
}
for(int i=0;i<=n+1;i++){
if(i==0||i==n+1){
for(int j=0;j<=m+1;j++){
Map[i][j]='.';
}
}else{
Map[i][0]='.';
Map[i][m+1]='.';
}
}
// cout<
アリ雲建駅-企業にインターネットの「速い」サービスを提供2020年に突然の疫病のため、多くの企業が深刻な衝撃を受け、疫病の衝撃力は伝統的な「純線下」業界に最も危害を及ぼし、インターネットの女王マリー・ミック(MaryMeeker)は4月17日に有名な年度インターネットトレンド報告書を発表した.報告書は、強力なインターネット上のオンラインとオフラインの融合能力を持つ企業が疫病の中で最もよく表現され、オンラインとオフラインの融合傾向はすでにしばらく存在しているが、疫病はこのような需要をさらに切実にしていると指摘した.もしあなたの企業が伝統的な純粋なラインの下の経験モデルに完全に依存しているならば、2020年にあなたは「必ず死ぬ」ことになります.巨大で、かつてないインターネット革命が到来しました.アリ雲建駅は各業界の復工・復産を支援するため、疫病期間中に「馬がひっきりなしに足を踏み入れる」ことは数万人の企業のために迅速に駅を建設し、彼らのために「オンラインとオフラインの融合」あるいは「純オンライン」のインターネット経営モデルに向かって邁進し、堅固な基礎を築いた.「雲・速成美駅」テンプレートは1日でオンラインになり、技術が分からなくても大丈夫で、タイプすればサイトを作ることができます.千セットのウェブサイトのテンプレートは無料で提供して、100元は公式サイトを建てることができて、1価はすべて包んで、いかなる隠れた消費がありません."云・企业の公式サイト"のカスタマイズは1周间でオンラインになることができて、ハイエンドのカスタマイズは駅を建てて、千元の公式サイトは自分で手を出す必要はありませんて、駅の専门家の1対1のウェブサイトの企画と设计、専门の安心の选択.疫病は、大きな波が砂を洗うので、毎回の危機の背後にはチャンスが隠されていて、危機が大きいほど、チャンスも大きくなります.大きな環境はすでに変わっています.もしあなたがこの大きな環境に迎合するために努力しなければ、あなたは必ず淘汰されます.阿里云は企业の建设を助けて、优遇は多くて、福祉は多くて、详しくは以下のリンクをクリックしてくださいhttps://www.aliyun.com/minisite/goods?userCode=tz7kl4ag
4 4
.$.$
.##.
#$#.
.#.#
34 4
.#$#
####
..$$
$$$$
7# include
using namespace std;
struct node{
int x;
int y;
char z;
};
bool cmp(int a,int b){
return a>b;
}
int dir[4][2]={0,-1,-1,0,0,1,1,0};
int vis[510][510];
char Map[510][510];
int main(){
int n,m;
cin>>n>>m;
int sum[250006]={0};
int t=-1;
char s;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>s;
Map[i][j]=s;
}
}
for(int i=0;i<=n+1;i++){
if(i==0||i==n+1){
for(int j=0;j<=m+1;j++){
Map[i][j]='.';
}
}else{
Map[i][0]='.';
Map[i][m+1]='.';
}
}
// cout<