【C++広さ検索】救助
1866 ワード
何の役にも立たないインデックスだと思います
キュー私は1篇の問題解を書いて説明したことがあって、見ます:【C++広さ検索入門】面積
これは私の第2篇の広捜題解で、まだ多くの不足があるかもしれませんが、皆さん、よろしくお愿いします.私と討論することを歓迎します.
タイトル
質問B:救出
時間制限:1 Secメモリ制限:128 MB
タイトルの説明
鉄塔尼号が遭難した!彼は助けを求める信号を出した.最寄りのコロンビア号からメッセージが届いた.時間は命だ.できるだけ早くそこに駆けつけなければならない.
偵察を通じて、コロンビア号は海洋図を手に入れた.この図は海洋部分をn*n個の比較的小さい単位に分化し,そのうち1で陸地,0で海洋と表記した.船は1つの格子から隣接する4つの格子に移動するしかありません.
できるだけ早く事故現場に着くために、コロンビア号は少なくともどのくらいの距離を歩かなければならない.
入力
第1の挙動nは、海洋地図を表すn*nの0、1行列である
最後の挙動はn未満の4つの整数で,それぞれコロンビア号と鉄塔尼号の位置を表す.
しゅつりょく
コロンビア号からタワーニ号までの最短距離.
サンプル入力
サンプル出力
ヒント
N<=1000
問題解
入力に長い時間がかかりましたので、入力の処理に注意してください.
キュー私は1篇の問題解を書いて説明したことがあって、見ます:【C++広さ検索入門】面積
これは私の第2篇の広捜題解で、まだ多くの不足があるかもしれませんが、皆さん、よろしくお愿いします.私と討論することを歓迎します.
タイトル
質問B:救出
時間制限:1 Secメモリ制限:128 MB
タイトルの説明
鉄塔尼号が遭難した!彼は助けを求める信号を出した.最寄りのコロンビア号からメッセージが届いた.時間は命だ.できるだけ早くそこに駆けつけなければならない.
偵察を通じて、コロンビア号は海洋図を手に入れた.この図は海洋部分をn*n個の比較的小さい単位に分化し,そのうち1で陸地,0で海洋と表記した.船は1つの格子から隣接する4つの格子に移動するしかありません.
できるだけ早く事故現場に着くために、コロンビア号は少なくともどのくらいの距離を歩かなければならない.
入力
第1の挙動nは、海洋地図を表すn*nの0、1行列である
最後の挙動はn未満の4つの整数で,それぞれコロンビア号と鉄塔尼号の位置を表す.
しゅつりょく
コロンビア号からタワーニ号までの最短距離.
サンプル入力
3
001
101
100
1 1 3 3
サンプル出力
4
ヒント
N<=1000
問題解
入力に長い時間がかかりましたので、入力の処理に注意してください.
#include
using namespace std;
struct hhh
{
int h,l,s;// , ,
}qwq[1000005];
int jz[1005][1005]={0},vis[1005][1005]={0};
int main()
{
int bh[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int head,tail,ax,ay,bx,by,flag=0,n,nx,ny;
char ch;
scanf("%d",&n);
// 001,,100 , 1,0,0, 100, ,
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(cin>>ch) jz[i][j]=ch-'0';
}
}
scanf("%d %d %d %d",&ax,&ay,&bx,&by);
//
head=1;tail=1;
qwq[tail].h=ax;
qwq[tail].l=ay;
qwq[tail].s=0;
tail++;
vis[ax][ay]=1;
while(headn||ny<1||ny>n)
continue;
if(jz[nx][ny]==0&&vis[nx][ny]==0)
{
vis[nx][ny]=1;
qwq[tail].h=nx;//
qwq[tail].l=ny;
qwq[tail].s=qwq[head].s+1;
tail++;
}
if(nx==bx&&ny==by)//
{
flag=1;break;
}
}
if(flag==1) break;
head++;//
}
//tail ( , -1)
cout<