poj 1915広さ優先遍歴
10115 ワード
poj 1915広さ優先遍歴
背景神話のようなチェスプレイヤーSomurolovさんは、騎士を一つの位置からすぐに別の位置に移動することができると主張しているが、他の人はだめだ.彼を負かすことができますか.問題は、騎士が別の場所から移動する最小限のステップ数を計算するプログラムを作成することです.そうすれば、Somurolovよりも速くなる機会があります.よく知られていないチェスかもしれないが、騎士の行動は図1に示すようになるかもしれない.入力はまず最初の行にnを入力し,n種類がある場合を表す.次はnスキームです.各シナリオには3行が含まれます.1行目は、1つの碁盤の長さL(4<=L<=300)を指定します.碁盤全体のサイズL*L.2行目と3行目は整数対(0,...,L-1)*を含みます.(0,...,L-1)騎士の開始位置と終了位置を指定します.整数対は空白で区切られています.出力騎士の行動を計算するには、入力ごとに開始点から終了点までの最低ステップ数を移動する必要があります.開始点と終了点が平等であれば、距離はゼロです.2.解題プロセス:解析プロセス:問題の意味を理解した後、これが最も短い可能性があることを発見しますパスの応用、しかし図のアルゴリズムのテーマを見た後に、更によく考えてみると、これは1本の広さが優先的に遍歴する応用で、広捜を利用して最短のパスを求めるのは比較的に簡単です.広さ優先で検索し,見つけたら検索の深さから必要な最小ステップ数を求めることができる.広さ優先のアルゴリズムはキューを使い、普段も練習しているので、アルゴリズムにも問題はありません.この問題のデータの入力問題は、比較的簡単です.しかし、記憶は少し面倒です.碁盤の大きさは4*4から300*300までで、スパンが大きいので、最大の2次元配列を定義して記憶するだけでは、多くの空間を浪費する可能性があります.また、キューに格納するのは1つの碁盤の格子なので、少なくとも2つの数を保存しなければなりません.便利のために、私は直接2つの整数型のキューを使って2つの下札を保存するのは難しくありません.プログラミングプロセス:具体的なプログラミングになったとき、検索の深さから必要な最小ステップ数をどのように求めるか、このステップの実現は面倒であることに気づいた.以前書いたint型キューでは直接実現するのが難しく,チェッカーのx,y座標のほかにチェッカーの歩数も記録するつもりだった.新しい構造体のキューを再定義するか、複数のキューを並列に使用するか、どちらも面倒です.だから私はC++に直接のキューがあれば使えると思いますが、私はC++はできません.最後にpojでjavaコードを提出できることに気づいて、来学期sunのscjp認証を受けなければならないことを考えて、javaを復習しなければなりません.だから、最後にjavaでやるつもりです.そこで、私はすぐにjavaでコードを編み出して、自分でテストしても合格しましたが、提出したときはメモリが溢れていました.長い間考えていたので、何が原因なのか、最初はsizeを手に入れた後、碁盤全体を建てました.このように多くのオブジェクトが生成され、自然に多くの役に立たないオブジェクトが多くのメモリを占めています.その後、必要に応じて碁格子を作る対象に変更しましたが、やはりメモリが少なくなりました.しかし、提出する時、運行ミスを発見しましたが、自分でテストしても大丈夫なので、長い間憂鬱でした.最後に、空のポインタの異常があるところを見つけて、やっと通過しました.
転載先:https://www.cnblogs.com/SSYYGAM/p/4509684.html
背景神話のようなチェスプレイヤーSomurolovさんは、騎士を一つの位置からすぐに別の位置に移動することができると主張しているが、他の人はだめだ.彼を負かすことができますか.問題は、騎士が別の場所から移動する最小限のステップ数を計算するプログラムを作成することです.そうすれば、Somurolovよりも速くなる機会があります.よく知られていないチェスかもしれないが、騎士の行動は図1に示すようになるかもしれない.入力はまず最初の行にnを入力し,n種類がある場合を表す.次はnスキームです.各シナリオには3行が含まれます.1行目は、1つの碁盤の長さL(4<=L<=300)を指定します.碁盤全体のサイズL*L.2行目と3行目は整数対(0,...,L-1)*を含みます.(0,...,L-1)騎士の開始位置と終了位置を指定します.整数対は空白で区切られています.出力騎士の行動を計算するには、入力ごとに開始点から終了点までの最低ステップ数を移動する必要があります.開始点と終了点が平等であれば、距離はゼロです.2.解題プロセス:解析プロセス:問題の意味を理解した後、これが最も短い可能性があることを発見しますパスの応用、しかし図のアルゴリズムのテーマを見た後に、更によく考えてみると、これは1本の広さが優先的に遍歴する応用で、広捜を利用して最短のパスを求めるのは比較的に簡単です.広さ優先で検索し,見つけたら検索の深さから必要な最小ステップ数を求めることができる.広さ優先のアルゴリズムはキューを使い、普段も練習しているので、アルゴリズムにも問題はありません.この問題のデータの入力問題は、比較的簡単です.しかし、記憶は少し面倒です.碁盤の大きさは4*4から300*300までで、スパンが大きいので、最大の2次元配列を定義して記憶するだけでは、多くの空間を浪費する可能性があります.また、キューに格納するのは1つの碁盤の格子なので、少なくとも2つの数を保存しなければなりません.便利のために、私は直接2つの整数型のキューを使って2つの下札を保存するのは難しくありません.プログラミングプロセス:具体的なプログラミングになったとき、検索の深さから必要な最小ステップ数をどのように求めるか、このステップの実現は面倒であることに気づいた.以前書いたint型キューでは直接実現するのが難しく,チェッカーのx,y座標のほかにチェッカーの歩数も記録するつもりだった.新しい構造体のキューを再定義するか、複数のキューを並列に使用するか、どちらも面倒です.だから私はC++に直接のキューがあれば使えると思いますが、私はC++はできません.最後にpojでjavaコードを提出できることに気づいて、来学期sunのscjp認証を受けなければならないことを考えて、javaを復習しなければなりません.だから、最後にjavaでやるつもりです.そこで、私はすぐにjavaでコードを編み出して、自分でテストしても合格しましたが、提出したときはメモリが溢れていました.長い間考えていたので、何が原因なのか、最初はsizeを手に入れた後、碁盤全体を建てました.このように多くのオブジェクトが生成され、自然に多くの役に立たないオブジェクトが多くのメモリを占めています.その後、必要に応じて碁格子を作る対象に変更しましたが、やはりメモリが少なくなりました.しかし、提出する時、運行ミスを発見しましたが、自分でテストしても大丈夫なので、長い間憂鬱でした.最後に、空のポインタの異常があるところを見つけて、やっと通過しました.
1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 int map[305][305],sx,sy,ex,ey,n,dist[305][305];
8 int a[8][2]= {1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1,-2,-1};
9 //1,1,-1,-1,2,2,-2,-2};
10 //2,-2,2,-2,1,-1,1,-1};
11 struct point
12 {
13 int xx,yy;
14 };
15 point pp,p;
16 int x,y;
17
18 int bfs()
19 {
20 queue q;// ， ？
21 memset(map,0,sizeof(map));
22 memset(dist,0,sizeof(dist));
23 pp.xx=sx;
24 pp.yy=sy;
25 map[sx][sy]=1;
26 q.push(pp);
27 int tx,ty;
28 while(!q.empty())
29 {
30 pp=q.front();
31 x=pp.xx;
32 y=pp.yy;//x y tx ty
33 q.pop();
34 if(x==ex&&y==ey)break;
35
36
37 for(int i=0; i<8; i++)
38 {
39 tx=x+a[i][0];
40 ty=y+a[i][1];
41 if(tx>=0&&ty>=0&&tx0)
42 {
43 dist[tx][ty]=dist[x][y]+1;
44 p.xx=tx;
45 p.yy=ty;
46 q.push(p);
47 map[tx][ty]=1;
48 }
49 }
50 }
51
52
53 }
54 int main()
55 {
56 int t;
57 scanf("%d",&t);
58 while(t--)
59 {
60 scanf("%d",&n);
61 scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
62 bfs();
63 printf("%d
",dist[ex][ey]);
64 }
65 return 0;
66 } 転載先:https://www.cnblogs.com/SSYYGAM/p/4509684.html