アルゴリズムコンテスト入門経典(第2版)-劉汝佳-第7章解題ソースコード(C++言語)(部分)
24574 ワード
例題7-1
本題では貧挙を採用し,貧挙を採用する際,1つはどの変数を貧挙するかに注意し,2つ目は貧挙変数の取値範囲を決定する.もちろん、値の範囲が小さいほど、時間が短くなります.
例題7-2
本題はサブストリングの始点と終点を窮挙し,最後の積をlong longで定義することに注意し,intの表現範囲が足りない.
例題7-3
本題はyを列挙し,xを計算する.
例題7-4
本題では遡及法を用いるが,列挙法を解答木と見なせば,解答木を減枝することである.
例題7-5
この問題の2つのreturn 0は精髄であり,サブストリングが重複しているかどうかを判断する際に,この方法がよりよい.
例題7-6
この問題は私が最初のコードの中で、枝を切っていないで、受け入れられて、次のコードは枝を切っています.
本で与える剪定方式により2回剪定を行った後、使用時間は従来の0.12から0.02に減少した.効果は明らかだ.
例題7-7
このトピックでは、バイナリ方式でサブセットを生成します.次に、サブセットを左サブツリーセットと右サブツリーセットに分けます.次に、それぞれ再帰的に木を建て、各木を構成する棒の長さを算出する.サブセットによって作成されたすべてのツリーの最大長をvectorに存在させ、最後にvectorで最も長いものを選択します.本題はかなり古典的だ.バイナリ生成サブセットを用いてツリーを構築する方法は非常に参考になる.
コードソース:本のコード倉庫.二次学習のためにコードを貼り付けます.
例題7-8
本題は本の中のコードを採用して、私は本の中のコードを注釈して、理解します.実は本題は,状態変数を1つ加えたBFSであり,BFSの基本構造を採用し,キューを用いて補助する.
練習問題7-9
本題では,まず図を再生成し,障害ではない格子を番号付けし,そのxとyを格納する.次に、障害ではない格子が一歩移動できる格子の座標、すなわちその隣接を計算して記憶し、bfsにおける探索ステップ数を減少させる.
例題7-10
IDA*例題、クリックでリンクを開くコードを使って、私はこのリンクのコードに注釈を行って、IDA*に対して学習を行います.中には勉強できるテクニックがたくさんあります.私はこの文章のコードを参考にして、自分の分からないところを書き直して、IDA*のフレームワークは総括の中で現れます.
例7-11
単純な列挙では,列挙前に計算規模が予想され,異なるデータに基づいて異なる列挙戦略を採用し,検索空間を低減する.
例題7-12
今回は状態更新の方法を使い始めましたが、アクセスした状態を記憶するのに苦労しました.8デジタルの問題に比べて、この問題は全部で27の値の変化があり、8デジタルの問題のように27の値を直接27の値に変えることはできません.無駄な検索がたくさん行われ、検索空間全体が大きすぎて、記憶するものが多すぎます.ただし、本題では、IDA*を使用する2つ目の方法を提供します.
1つ目:ステータススペース検索(半製品)
2つ目は、IDA*を採用しています.ここでH関数の設計を参考にしていますが、最初に自分で設計したH関数がタイムアウトするので問題が発生しました.このテーマは実際には1次元配列として番号付けして保存することができ、A-Hの操作を行う上で、実際にインデックスを直接リストすることができ、コード量を減らすことができますが、私は2次元配列を修正する方法を採用しています.明らかに面倒です.これらのところはみな参考に値する.IDA*を使用すると、DFSの操作であるため、出力パスに役立ちますが、ステータススペース法を使用して親ノードを格納すると、格納に十分なスペースがない場合が多いです.
例題7-12
この問題の解法は古典的で,回転,反転などの操作にも関与している.本文はブログを参照してリンクを開く解法とコードをクリックし、コードに対して注釈学習を行う.データ上では,このノードにアクセスしたことがないと判断するために,2層のsetを用いて格納する.非常に参考になる.本題は大規模な問題を小規模な問題に分解し,第8章で学ぶべきである.
練習問題7-1
本題ではBFSを用いて連通性を判断し,DFSを用いて経路を探す.
練習問題7-2(WA)
本題はdfs+枝切りで、題意がはっきり理解されていないため、ずっとWAになっています.最終的には十分なテストデータがないので、一旦諦めて次の問題に進みます.
本題では貧挙を採用し,貧挙を採用する際,1つはどの変数を貧挙するかに注意し,2つ目は貧挙変数の取値範囲を決定する.もちろん、値の範囲が小さいほど、時間が短くなります.
#include
#include
using namespace std;
void int2char(int x,int xs[])
{
for(int i=4;i>0;i--)
{
xs[i]=x%10;
x=x/10;
}
xs[0]=x;
}
bool check(int xs[],int ys[])
{
int cnt[10];
memset(cnt,0,sizeof(cnt));
for(int i=0;i<5;i++)
{
if(xs[i]>=10||ys[i]>=10||++cnt[xs[i]]>1||++cnt[ys[i]]>1)
return false;
}
return true;
}
void printres(int xs[],int ys[],int n)
{
for(int i=0;i<5;i++)
cout<>n&&n)
{
if(flag++>0)
cout< 例題7-2
本題はサブストリングの始点と終点を窮挙し,最後の積をlong longで定義することに注意し,intの表現範囲が足りない.
#include
using namespace std;
long long cal(int s,int e,int in[])
{
long long tmp=1;
for(int i=s;i<=e;i++)
tmp=tmp*in[i];
return tmp;
}
int main()
{
//freopen("datain.txt","r",stdin);
//freopen("dataout.txt","w",stdout);
int inlen,in[18],rnd=1;
while(cin>>inlen&&inlen)
{
long long maxp=0,tmp;
for(int i=0;i>in[i];
for(int start=0;start 例題7-3
本題はyを列挙し,xを計算する.
#include
#include
using namespace std;
const int maxn=1000;
int main()
{
//freopen("datain.txt","r",stdin);
//freopen("dataout.txt","w",stdout);
long long k;
while(cin>>k&&k)
{
int kans[maxn],xans[maxn],yans[maxn];
int len=0;
for(int y=k+1;y<=2*k;y++)
{
int x = k*y;
if (x % (y-k) == 0) {
x /= (y-k);
xans[len]=x;
yans[len]=y;
kans[len]=k;
len++;
}
}
cout< 例題7-4
本題では遡及法を用いるが,列挙法を解答木と見なせば,解答木を減枝することである.
#include
#include
#include
using namespace std;
int n,isp[40],vis[20],A[20];
int is_prime (int n)
{
int flag,i;
flag=1;
for(i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
flag=0;
break;
}
if(n%i==0)
{
flag=0;
break;
}
}
return flag;
}
void dfs(int cur)
{
if(cur==n&&isp[A[0]+A[n-1]])
{
for(int i=0;i>n&&n)
{
if(rnd>1)
cout< 例題7-5
この問題の2つのreturn 0は精髄であり,サブストリングが重複しているかどうかを判断する際に,この方法がよりよい.
#include
#include
int n,L,S[100],cnt=0;
int dfs(int cur)
{
if(cnt++==n)
{
for(int i=0;i 例題7-6
この問題は私が最初のコードの中で、枝を切っていないで、受け入れられて、次のコードは枝を切っています.
#include
#include
#include
#include
#include
using namespace std;
const int maxn=30;
int minbd=30,G[maxn][maxn],op[maxn];
int n=0;
int computebd(int *A,int *node,int cur,int n)//n A
{
int lenth=0;
for(int i=0;i1)
// {
// int tmp;
// tmp=computebd(A,node,cur,n);
// if(tmp>minbd)
// return;
// }
for(int i=0;i>tmp)
{
nei1 = tmp-'A';
nodetmp[nei1]=1;
while(ss>>tmp&&tmp!=';')
{
if(tmp!=':'&&tmp!=' ')
{
nei2 = tmp -'A';
nodetmp[nei2]=1;
G[nei1][nei2]=1;
G[nei2][nei1]=1;
}
}
}
for(int i=0;i "< 本で与える剪定方式により2回剪定を行った後、使用時間は従来の0.12から0.02に減少した.効果は明らかだ.
#include
#include
#include
#include
#include
using namespace std;
const int maxn=30;
int minbd=30,G[maxn][maxn],op[maxn];
int n=0;
int computebd(int *A,int *node,int cur,int n)
{
int lenth=0;
for(int i=0;i1)// 。
{
int tmp;
tmp=computebd(A,node,cur,n);
if(tmp>minbd)
return;
}
for(int i=0;i>tmp)
{
nei1 = tmp-'A';
nodetmp[nei1]=1;
while(ss>>tmp&&tmp!=';')
{
if(tmp!=':'&&tmp!=' ')
{
nei2 = tmp -'A';
nodetmp[nei2]=1;
G[nei1][nei2]=1;
G[nei2][nei1]=1;
}
}
}
for(int i=0;i "< 例題7-7
このトピックでは、バイナリ方式でサブセットを生成します.次に、サブセットを左サブツリーセットと右サブツリーセットに分けます.次に、それぞれ再帰的に木を建て、各木を構成する棒の長さを算出する.サブセットによって作成されたすべてのツリーの最大長をvectorに存在させ、最後にvectorで最も長いものを選択します.本題はかなり古典的だ.バイナリ生成サブセットを用いてツリーを構築する方法は非常に参考になる.
コードソース:本のコード倉庫.二次学習のためにコードを貼り付けます.
// UVa1354 Mobile Computing
// Rujia Liu
#include
#include
#include
using namespace std;
struct Tree {
double L, R; // distance from the root to the leftmost/rightmost point
Tree():L(0),R(0) {}
};
const int maxn = 6;
int n, vis[1< tree[1< 例題7-8
本題は本の中のコードを採用して、私は本の中のコードを注釈して、理解します.実は本題は,状態変数を1つ加えたBFSであり,BFSの基本構造を採用し,キューを用いて補助する.
#include
#include
#include
using namespace std;
struct Node
{
int v[3],dist;// 3 ，dist 。
bool operator < (const Node& rhs) const {
return dist > rhs.dist;// ，
}
};
const int maxn=200+5;
int vis[maxn][maxn],cap[3],ans[maxn];
//vis ， 。
void update_ans (const Node& u)
{
for(int i=0;i<3;i++)
{
int d = u.v[i];
if(ans[d]<0||u.dist q;
Node start;
start.dist=0;
start.v[0]=0;start.v[1]=0;start.v[2]=c;
// ， C 。
q.push(start);
vis[0][0]=1;
while(!q.empty())
{
Node u = q.top(); q.pop();
update_ans(u);
if(ans[d]>=0) break;// ， d 。
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(i!=j)// , i j 。
{
if(u.v[i]==0 || u.v[j]==cap[j]) continue;
// i j ， 。
int amount = min(cap[j],u.v[i]+u.v[j])-u.v[j];
// ， 。
Node u2;
memcpy(&u2,&u,sizeof(u));
u2.dist=u.dist+amount;
u2.v[i]-=amount;
u2.v[j]+=amount;
if(!vis[u2.v[0]][u2.v[1]])
{
vis[u2.v[0]][u2.v[1]]=1;
q.push(u2);
}
}
}
while(d>=0)
{
if(ans[d]>=0)
{
printf("%d %d
",ans[d],d);
return;
}
d--;// d， 1， 。
}
}
int main()
{
int T,a,b,c,d;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
solve(a,b,c,d);
}
return 0;
} 練習問題7-9
本題では,まず図を再生成し,障害ではない格子を番号付けし,そのxとyを格納する.次に、障害ではない格子が一歩移動できる格子の座標、すなわちその隣接を計算して記憶し、bfsにおける探索ステップ数を減少させる.
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 256;
int dx[] = {-1,1,0,0,0};
int dy[] = {0,0,0,1,-1};
int s[3],e[3];
int neicnt[maxn],nei[maxn][maxn];
int vis[maxn][maxn][maxn];
struct Node
{
int cntx,cnty,cntz;
int d;
Node():cntx(-1),cnty(-1),cntz(-1),d(-1) {}
};
bool judge(int cntx,int cnty,int ncntx,int ncnty)
{
return ncntx==ncnty||(cntx==ncnty&&cnty==ncntx);
}
int bfs()
{
queue q;
Node start;
start.cntx=s[0];
start.cnty=s[1];
start.cntz=s[2];
start.d=0;
memset(vis,-1,sizeof(vis));
q.push(start);
while(!q.empty())
{
Node u = q.front();
q.pop();
if(u.cntx==e[0]&&u.cnty==e[1]&&u.cntz==e[2]) return u.d;
for (int i=0;i>w>>h>>n&&h)
{
char map[maxn][maxn];
int new_map[maxn][maxn];
int idx[maxn],idy[maxn];
int cnt=0;
getchar();
for(int i=0;i=0&&ny>=0)
{
nei[i][neicnt[i]++]=new_map[nx][ny];
}
}
}
// ， 。
if(n<=2)
{
neicnt[cnt]=1;nei[cnt][0]=cnt;s[2]=e[2]=cnt++;
}
if(n<=1)
{
neicnt[cnt]=1;nei[cnt][0]=cnt;s[1]=e[1]=cnt++;
}
cout< 例題7-10
IDA*例題、クリックでリンクを開くコードを使って、私はこのリンクのコードに注釈を行って、IDA*に対して学習を行います.中には勉強できるテクニックがたくさんあります.私はこの文章のコードを参考にして、自分の分からないところを書き直して、IDA*のフレームワークは総括の中で現れます.
#include
//
using namespace std;
struct State{
int a[12];
}; //
int n, kase = 0, maxd;
//n ，kase ，maxd IDA* 。
int getH(State cur)
{
int cnt = 0;
for(int i = 0; i < n-1; ++i)
if(cur.a[i]+1 != cur.a[i+1])
cnt++;
return cnt;
}// ,
bool DFS(int d, State u)
{
int H = getH(u);
if(d == maxd) return H == 0;
if(3*d + H > 3*maxd) return false;
int board[12];
for(int len = 1;len> n && n){
State beg;
for(int i = 0; i < n; ++i)
cin >> beg.a[i];
for(maxd = 0; ; ++maxd)
if(DFS(0, beg))
break;
printf("Case %d: %d
", ++kase, maxd);
}
return 0;
} 例7-11
単純な列挙では,列挙前に計算規模が予想され,異なるデータに基づいて異なる列挙戦略を採用し,検索空間を低減する.
#include
using namespace std;
int main()
{
//freopen("datain.txt","r",stdin);
//freopen("dataout.txt","w",stdout);
ios::sync_with_stdio(false);
int T,rnd=1;
cin>>T;
while(T--)
{
long long N,S1,V1,S2,V2;
long long bestvalue=0;
cin>>N>>S1>>V1>>S2>>V2;
if(N/S1<65536)
{
for(int i=0;i*S1<=N;i++)
{
long long value = i*V1+((N-i*S1)/S2)*V2;
bestvalue=max(bestvalue,value);
}
}
else if(N/S2<65536)
{
for(long long i=0;i*S2<=N;i++)
{
if(i*S2<=N)
{
long long value = i*V2+((N-i*S2)/S1)*V1;
bestvalue=max(bestvalue,value);
}
}
}
else
{
if (S2*V1 < S1*V2)
{
for(int i=0;i 例題7-12
今回は状態更新の方法を使い始めましたが、アクセスした状態を記憶するのに苦労しました.8デジタルの問題に比べて、この問題は全部で27の値の変化があり、8デジタルの問題のように27の値を直接27の値に変えることはできません.無駄な検索がたくさん行われ、検索空間全体が大きすぎて、記憶するものが多すぎます.ただし、本題では、IDA*を使用する2つ目の方法を提供します.
1つ目:ステータススペース検索(半製品)
#include
using namespace std;
const int maxn = 60000;
struct State
{
int board[8][8];
char operate;
int fid;
int id;
int d;
};
State state[maxn];
int cnt=0;
void Rotation(State &s,int rc,int flag)
//1 ，2 ，3 ，4 。
{
if(flag==1)
{
int tmp = s.board[0][rc];
for(int i=0;i<6;i++)
{
s.board[i][rc]=s.board[i+1][rc];
}
s.board[6][rc]=tmp;
}
else if(flag==2)
{
int tmp = s.board[6][rc];
for(int i=6;i>0;i--)
{
s.board[i][rc]=s.board[i-1][rc];
}
s.board[0][rc]=tmp;
}
else if(flag==3)
{
int tmp = s.board[rc][6];
for(int i=6;i>0;i--)
{
s.board[rc][i]=s.board[rc][i-1];
}
s.board[rc][0]=tmp;
}
else if (flag==4)
{
int tmp = s.board[rc][0];
for(int i=0;i<6;i++)
{
s.board[rc][i]=s.board[rc][i+1];
}
s.board[rc][6]=tmp;
}
}
void operation(State &s,char x)
{
if(x=='A')
{
Rotation(s,2,1);
}
else if (x=='B')
{
Rotation(s,4,1);
}
else if (x=='C')
{
Rotation(s,2,3);
}
else if (x=='D')
{
Rotation(s,4,3);
}
else if (x=='E')
{
Rotation(s,4,2);
}
else if (x=='F')
{
Rotation(s,2,2);
}
else if (x=='G')
{
Rotation(s,4,4);
}
else if (x=='H')
{
Rotation(s,2,4);
}
}
bool isdone(State &s,int num)
{
if(s.board[3][2]!=num||s.board[3][4]!=num)
{
return false;
}
else
{
for(int i=2;i<=4;i++)
{
if(s.board[2][i]!=num)
{
return false;
}
if(s.board[4][i]!=num)
{
return false;
}
}
}
return true;
}
State solve(State &s,int num)
{
if(isdone(s,num)) return s;
queue qs;
qs.push(s);
while(!qs.empty())
{
State s1 = qs.front();
if(s1.d>5) return s1;
qs.pop();
for(int i=0;i<=7;i++)
{
State s2;
memcpy(&s2,&s1,sizeof(s1));
char op = 'A'+ i;
operation(s2,op);
s2.operate = op;
s2.d=s1.d+1;
s2.fid=s1.id;
s2.id=cnt;
state[cnt++]=s2;
if(isdone(s2,num)) return s2;
qs.push(s2);
}
}
}
int main()
{
freopen("datain.txt","r",stdin);
int map[8][8];
memset(map,0,sizeof(map));
while(cin>>map[0][2]&&map[0][2])
{
cin>>map[0][4];
cin>>map[1][2]>>map[1][4];
for(int i=0;i<7;i++)
{
cin>>map[2][i];
}
cin>>map[3][2]>>map[3][4];
for(int i=0;i<7;i++)
{
cin>>map[4][i];
}
cin>>map[5][2]>>map[5][4];
cin>>map[6][2]>>map[6][4];
cnt=0;
State ans[4];
for(int num=1;num<=3;num++)
{
State root;
memset(root.board,0,sizeof(root.board));
for(int i=0;i<7;i++)
for (int j=0;j<7;j++)
if(map[i][j]==num)
root.board[i][j]=num;
root.d = 0;
root.id = cnt;
root.fid = 0;
state[cnt++]=root;
ans[num]=solve(root,num);
}
int mind=10;
int index;
for(int i=1;i<=3;i++)
{
if(mind>ans[i].d)
{
mind=ans[i].d;
index = i;
}
}
char charo[maxn];
int j=0;
if (ans[index].d==0)
{
cout<=0;i--)
{
cout< 2つ目は、IDA*を採用しています.ここでH関数の設計を参考にしていますが、最初に自分で設計したH関数がタイムアウトするので問題が発生しました.このテーマは実際には1次元配列として番号付けして保存することができ、A-Hの操作を行う上で、実際にインデックスを直接リストすることができ、コード量を減らすことができますが、私は2次元配列を修正する方法を採用しています.明らかに面倒です.これらのところはみな参考に値する.IDA*を使用すると、DFSの操作であるため、出力パスに役立ちますが、ステータススペース法を使用して親ノードを格納すると、格納に十分なスペースがない場合が多いです.
#include
using namespace std;
const int maxn = 60000;
struct State
{
int board[8][8];
};
int maxd,fsnum;
char fs[maxn];
void Rotation(State &s,int rc,int flag)
//1 ，2 ，3 ，4 。
{
if(flag==1)
{
int tmp = s.board[0][rc];
for(int i=0;i<6;i++)
{
s.board[i][rc]=s.board[i+1][rc];
}
s.board[6][rc]=tmp;
}
else if(flag==2)
{
int tmp = s.board[6][rc];
for(int i=6;i>0;i--)
{
s.board[i][rc]=s.board[i-1][rc];
}
s.board[0][rc]=tmp;
}
else if(flag==3)
{
int tmp = s.board[rc][6];
for(int i=6;i>0;i--)
{
s.board[rc][i]=s.board[rc][i-1];
}
s.board[rc][0]=tmp;
}
else if (flag==4)
{
int tmp = s.board[rc][0];
for(int i=0;i<6;i++)
{
s.board[rc][i]=s.board[rc][i+1];
}
s.board[rc][6]=tmp;
}
}
void operation(State &s,char x)
{
if(x=='A')
{
Rotation(s,2,1);
}
else if (x=='B')
{
Rotation(s,4,1);
}
else if (x=='C')
{
Rotation(s,2,3);
}
else if (x=='D')
{
Rotation(s,4,3);
}
else if (x=='E')
{
Rotation(s,4,2);
}
else if (x=='F')
{
Rotation(s,2,2);
}
else if (x=='G')
{
Rotation(s,4,4);
}
else if (x=='H')
{
Rotation(s,2,4);
}
}
int isdone(State &s)
{
for (int num=1;num<=3;num++)
{
bool flag = true;
if(s.board[3][2]!=num||s.board[3][4]!=num)
{
flag = false;
}
else
{
for(int i=2;i<=4;i++)
{
if(s.board[2][i]!=num)
{
flag = false;
}
if(s.board[4][i]!=num)
{
flag = false;
}
}
}
if(flag)
{
return num;
}
}
return 0;
}
int getH(State &s,int num)
{
int cnt = 0;
for(int i=2;i<=4;i++)
{
if(s.board[2][i]!=num)
cnt++;
if(s.board[3][i]!=num&&i!=3)
cnt++;
if(s.board[4][i]!=num)
cnt++;
}
return cnt;
}
int get_h(State &s)
{
return min(getH(s,1),min(getH(s,2),getH(s,3)));
}
bool dfs(int d,State s)
{
int h=get_h(s);
if(d==maxd)
{
fsnum=isdone(s);
if(fsnum)
{
if(d==0)
{
cout<maxd) return false;
for(int i=0;i<=7;i++)
{
State s2;
memcpy(&s2,&s,sizeof(s));
char op = 'A'+ i;
operation(s2,op);
fs[d]=op;
if(dfs(d+1,s2)) return true;
}
return false;
}
int main()
{
//freopen("datain.txt","r",stdin);
int map[8][8];
memset(map,0,sizeof(map));
while(cin>>map[0][2]&&map[0][2])
{
cin>>map[0][4];
cin>>map[1][2]>>map[1][4];
for(int i=0;i<7;i++)
{
cin>>map[2][i];
}
cin>>map[3][2]>>map[3][4];
for(int i=0;i<7;i++)
{
cin>>map[4][i];
}
cin>>map[5][2]>>map[5][4];
cin>>map[6][2]>>map[6][4];
bool flag=false;
for(maxd=0; ;maxd++)
{
State root;
memcpy(root.board,map,sizeof(map));
flag=dfs(0,root);
if(flag)
{
cout< 例題7-12
この問題の解法は古典的で,回転,反転などの操作にも関与している.本文はブログを参照してリンクを開く解法とコードをクリックし、コードに対して注釈学習を行う.データ上では,このノードにアクセスしたことがないと判断するために,2層のsetを用いて格納する.非常に参考になる.本題は大規模な問題を小規模な問題に分解し,第8章で学ぶべきである.
#include
using namespace std;
struct Cell
{
int x,y;
Cell(int x=0,int y=0):x(x),y(y){};
bool operator < (const Cell & rhs) const
{
return x Polyomino;
// set Polyomino
#define FOR_CELL(c,p) for(Polyomino::const_iterator c = (p).begin();c != (p).end(); c++)
inline Polyomino normalize(const Polyomino &p)// ，
{
int minX = p.begin()->x,minY=p.begin()->y;
FOR_CELL(c,p)
{
minX=min(minX,c->x);
minY=min(minY,c->y);
}
Polyomino p2;
FOR_CELL(c,p)
{
p2.insert(Cell(c->x-minX,c->y-minY));
}
return p2;
}
inline Polyomino rotate(const Polyomino &p)
// ， 90
{
Polyomino p2;
FOR_CELL(c,p)
{
p2.insert(Cell(c->y,-c->x));
}
return normalize(p2);
}
inline Polyomino flip(const Polyomino &p)
{
// X
Polyomino p2;
FOR_CELL(c,p)
{
p2.insert(Cell(c->x,-c->y));
}
return normalize(p2);
}
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int maxn=10;
set poly[maxn+1];
int ans[maxn+1][maxn+1][maxn+1];
void check_polyomino(const Polyomino& p0,const Cell& c)
{
// C p0
Polyomino p = p0;
p.insert(c);
p= normalize(p);
int n=p.size();//n n 。
for (int i=0;i<4;i++)
{
if(poly[n].count(p)!=0) return;
p = rotate(p);
}
p=flip(p);
for (int i=0;i<4;i++)
{
if(poly[n].count(p)!=0) return;
p = rotate(p);
}
poly[n].insert(p);
// ， ， 。
}
void generate()
{
Polyomino s;
s.insert(Cell(0,0));
poly[1].insert(s);
// 。
for (int n=2;n<=maxn;n++)
{
for(set::iterator p=poly[n-1].begin();p!=poly[n-1].end();++p)
FOR_CELL(c,*p)
for (int dir=0;dir<4;dir++)
{
Cell newc(c->x+dx[dir],c->y+dy[dir]);
if(p->count(newc)==0)
check_polyomino(*p,newc);
}
}
for(int n=1;n<=maxn;n++)
for(int w=1;w<=maxn;w++)
for(int h=1;h<=maxn;h++)
{//
int cnt=0;
for(set::iterator p=poly[n].begin();p!=poly[n].end();++p)
{
int maxX=0,maxY=0;
FOR_CELL(c,*p)
{
maxX=max(maxX,c->x);
maxY=max(maxY,c->y);
}
if(min(maxX,maxY)>n>>w>>h&&n)
{
cout< | 練習問題7-1
本題ではBFSを用いて連通性を判断し,DFSを用いて経路を探す.
#include
using namespace std;
const int maxn=100;
int mapp[maxn][maxn];
int node=1,endnode;
int vis[maxn];
int sum=0;
int added[maxn];
void dfs(int d,int* anstmp)
{
if(anstmp[d]==endnode)
{
for(int i=0;i q;
q.push(1);
while(!q.empty())
{
int ne=q.front();
q.pop();
for (int i=1;i<=node;i++)
{
if(mapp[ne][i]==1&&added[i]!=1)
{
if(i==endnode)
return true;
else
{
added[i]=1;
q.push(i);
}
}
}
}
return false;
}
int main()
{
//freopen("datain.txt","r",stdin);
//freopen("dataout.txt","w",stdout);
int rnd=1;
while(cin>>endnode)
{
int r,c;
memset(mapp,0,sizeof(mapp));
sum=0;
node=1;
while(cin>>r>>c&&r)
{
node=max(c,max(node,r));
mapp[r][c]=1;
mapp[c][r]=1;
}
int anstmp[maxn];
memset(vis,0,sizeof(vis));
anstmp[0]=1;
vis[1]=1;
cout< 練習問題7-2(WA)
本題はdfs+枝切りで、題意がはっきり理解されていないため、ずっとWAになっています.最終的には十分なテストデータがないので、一旦諦めて次の問題に進みます.
#include
using namespace std;
const int maxn = 1000;
int center=maxn/2;
int mapp[maxn][maxn],vis[maxn][maxn];
int sumr=0,maxd;
struct State
{
int x,y;
int dir;
};
char news[]={'e','n','s','w'};
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
void dfs(int d,State *route)
{
if(route[d].x==center&&route[d].y==center&&d==maxd)
{
for(int i=1;i<=d;i++)
cout<>T;
while(T--)
{
sumr=0;
memset(mapp,0,sizeof(mapp));
memset(vis,0,sizeof(vis));
int numb;
cin>>maxd>>numb;
for(int i=0;i>x>>y;
nx=center+x;
ny=center+y;
mapp[nx][ny]=1;
}
State route[maxn];
State br;
br.x=center;
br.y=center;
br.dir=4;
memcpy(&route[0],&br,sizeof(br));
dfs(0,route);
if(sumr==0)
cout<