POJ 2585 Window Pains(トポロジーソート判定)
3283 ワード
POJ 2585 Window Pains(トポロジーソート判定)
http://poj.org/problem?id=2585
タイトル:
あなたに1つの4*4の碁盤の窓をあげて、今コンピュータの上で9つの応用があって、各応用は固定の2*2の正方形のグリッドの位置を占有します.あなたは異なる順序で9つの応用を操作することを通じて(通って)4*4の窓の現在表示する内容(数字の代表)を異なって、今あなたに1つの4*4の碁盤の窓の内容をあげて、あなたにこの内容が合法かどうかを聞きます.
分析:
実は本題はトポロジーの順序付けが存在するかどうかを判定する問題です.9つの小さなウィンドウアプリケーションを9つの点と見なして、4*4の碁盤にとって:
(1,2)この四角い格子が現在置かれているのは2の数字で、もともと(1,2)四角い格子は私たちが置くことができる数は1と2の2つの数があり、今2を置いて、1アプリケーション->2アプリケーションから1つのエッジがあることを説明します.(つまり、アプリケーション1は先に置くべきで、アプリケーション2は後で置くので、アプリケーション2はアプリケーション1を隠すことができます).
ここで(2,2)この四角形を見ると,この四角形は5であるが,この四角形の本来の応用は1,2,4,5の4つの応用である.現在現れた応用は5であり,5が最後にやっと置かれた応用であることを示している.だから,応用1−>5の応用から1つの有向辺があり,2−>5,4−>5から1つの有向辺があることが分かる.
そして我々はすべての4*4格子を分析することによってすべての有向辺を得ることができ、G[10][10]配列とin[10]配列を得ることができる.
次に、有向図について、トポロジーソートが可能かどうかをどのように判断しますか?ここではトポロジーの結果を出力する必要はありません.私たちはこの図を分解するだけでいいです.この図が最終的に完全に分解できるかどうかを見てみましょう.(具体的な過程はデータ構造C言語版、厳蔚敏という本で詳しく紹介されています.私のソースコードを見てもわかるはずです)
分解プロセスは、初期状態から1つの入度0の点を選択するたびに、それから出たすべての辺を削除し、これらの辺に関連する点の入度を減少する.入度0の点位置が見つからないまで削除する.
最後の図における点の度合いが0でない場合、図にループがある、トポロジーソートができないことを示す.
この問題はまた、(1,2)格子が1または2しか表示できない場合、3,4,5などの数字を表示することは不可能であると仮定する.入力にはこのようなデータはない.
注意:ソースコードに実装は0-8の数字表示が適用され、碁盤4*4も0からカウントする.プログラムにはエッジが繰り返し追加される可能性があり、必ず現在のG[i][j]が==0であるかどうかを判断する.
ACコード:
http://poj.org/problem?id=2585
タイトル:
あなたに1つの4*4の碁盤の窓をあげて、今コンピュータの上で9つの応用があって、各応用は固定の2*2の正方形のグリッドの位置を占有します.あなたは異なる順序で9つの応用を操作することを通じて(通って)4*4の窓の現在表示する内容(数字の代表)を異なって、今あなたに1つの4*4の碁盤の窓の内容をあげて、あなたにこの内容が合法かどうかを聞きます.
分析:
実は本題はトポロジーの順序付けが存在するかどうかを判定する問題です.9つの小さなウィンドウアプリケーションを9つの点と見なして、4*4の碁盤にとって:
(1,2)この四角い格子が現在置かれているのは2の数字で、もともと(1,2)四角い格子は私たちが置くことができる数は1と2の2つの数があり、今2を置いて、1アプリケーション->2アプリケーションから1つのエッジがあることを説明します.(つまり、アプリケーション1は先に置くべきで、アプリケーション2は後で置くので、アプリケーション2はアプリケーション1を隠すことができます).
ここで(2,2)この四角形を見ると,この四角形は5であるが,この四角形の本来の応用は1,2,4,5の4つの応用である.現在現れた応用は5であり,5が最後にやっと置かれた応用であることを示している.だから,応用1−>5の応用から1つの有向辺があり,2−>5,4−>5から1つの有向辺があることが分かる.
そして我々はすべての4*4格子を分析することによってすべての有向辺を得ることができ、G[10][10]配列とin[10]配列を得ることができる.
次に、有向図について、トポロジーソートが可能かどうかをどのように判断しますか?ここではトポロジーの結果を出力する必要はありません.私たちはこの図を分解するだけでいいです.この図が最終的に完全に分解できるかどうかを見てみましょう.(具体的な過程はデータ構造C言語版、厳蔚敏という本で詳しく紹介されています.私のソースコードを見てもわかるはずです)
分解プロセスは、初期状態から1つの入度0の点を選択するたびに、それから出たすべての辺を削除し、これらの辺に関連する点の入度を減少する.入度0の点位置が見つからないまで削除する.
最後の図における点の度合いが0でない場合、図にループがある、トポロジーソートができないことを示す.
この問題はまた、(1,2)格子が1または2しか表示できない場合、3,4,5などの数字を表示することは不可能であると仮定する.入力にはこのようなデータはない.
注意:ソースコードに実装は0-8の数字表示が適用され、碁盤4*4も0からカウントする.プログラムにはエッジが繰り返し追加される可能性があり、必ず現在のG[i][j]が==0であるかどうかを判断する.
ACコード:
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=10;
vector<int> value[maxn][maxn];
int dr[]={0,1,0,1};// , , ,
int dc[]={0,0,1,1};
int G[maxn][maxn]; //
int in[maxn]; //
bool topo()
{
queue<int> Q;
for(int i=0;i<9;i++)
if(in[i]==0) Q.push(i);
int sum=0;// 0
while(!Q.empty())
{
int u=Q.front(); Q.pop();
for(int v=0;v<9;v++)if(G[u][v])
{
G[u][v]=0;
if(--in[v]==0) Q.push(v);
}
sum++;
}
return sum==9;
}
int main()
{
for(int i=0;i<9;i++) // 0-8 vector
{
int r=i/3, c=i%3; //i (r,c)
for(int dir=0;dir<4;dir++) //i 3
{
int nr=r+dr[dir], nc=c+dc[dir];
value[nr][nc].push_back(i); // i vector
}
}
char str[100];
while(scanf("%s",str)==1&&str[0]!='E')
{
memset(G,0,sizeof(G));
memset(in,0,sizeof(in));
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
int v;
scanf("%d",&v);
v--;
for(int k=0;k<value[i][j].size();k++)
if((value[i][j])[k]!=v)//
{
int x=(value[i][j])[k];
if(G[x][v]==0)// ,
{
in[v]++;
G[x][v]=1;
}
//printf(" :(%d,%d), :%d v=%d, %d %d
",i,j,x,v,v,in[v]);
}
}
if(topo()) printf("THESE WINDOWS ARE CLEAN
");
else printf("THESE WINDOWS ARE BROKEN
");
scanf("%s",str);
}
return 0;
}