【例题 6-19 UVA - 1572】Self-Assembly

在这里输入题意

【题解】

旋转和翻转,会发现。
如果可以顺着某个方向一直放的话。
总是能转换成往下或者往右连的。
则只要能够出现一个连接顺序的循环,则总是有解的。
->转化成图论模型
如果一个正方形有A+
另外一个正方形有A-B+C+D-
那么从A+连3条边分别到B+,C+,D-
按照这样的方式连,如果能出现一个环的话,肯定是有解的
->有一条边,就已经说明能够新增加一个正方形了。

拓扑排序判环即可

【代码】

/*

  	1.Shoud it use long long ?

  	2.Have you ever test several sample(at least therr) yourself?

  	3.Can you promise that the solution is right? At least,the main ideal

  	4.use the puts("") or putchar() or printf and such things?

  	5.init the used array or any value?

*/

#include <bits/stdc++.h>

using namespace std;

const int N = 52;

const int NN = (int) 4e4;

int n,tot;

map <string,int> mmap;

int g[N+10][N+10],du[N+10],num;

bool bo[N+10];

vector <int> v[NN+100];

queue <int> dl;

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("F:\\c++source\\rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

	for (char i = 'A';i <= 'Z';i++){

		string temp ="";

		temp+= i;temp += '-';

		mmap[temp] = ++tot;

	}

	for (char i = 'A';i <= 'Z';i++){

		string temp = "";

		temp += i;temp += '+';

		mmap[temp] = ++tot;

	}

	for (int i = 1;i <= NN;i++) v[i].resize(4);

	while ( cin >> n ){

		memset(g,0,sizeof g);

		memset(du,0,sizeof du);

	    memset(bo,0,sizeof bo);

    	for (int ii = 1;ii <= n;ii++){

    		string s;

    		cin >> s;

    		string temp = "";

    		for (int i = 0,j = 0;i < 7;i+=2,j++){

    		 	temp = s.substr(i,2);

				v[ii][j] = mmap[temp];

				bo[v[ii][j]] = 1;

    	 	}

    	}

    	for (int ii = 1;ii <= n;ii++){

    	 	for (int i = 0;i < 4;i++){

    			if (v[ii][i]==0) continue;

    		 	int x = (v[ii][i]>26)?(v[ii][i]-26):(v[ii][i]+26);

    		 	if (!bo[x]) continue;

    		 	for (int j = 0;j <4 ;j++)

    		 		if (i!=j){

    		 		 	int  y = v[ii][j];

    		 		 	if (y==0) continue;

    		 		 	if (!g[x][y]){

    		 		 	 	du[y]++;

    		 		 	}

    		 		 	g[x][y] = 1;

    		 		}

			}

	   }

	   num = 52;

	   for (int i = 1;i <= 52;i++)

	       if (du[i]==0){

	        	dl.push(i);

	        	du[i] = -1;

	       }

       while (!dl.empty()){

       		num--;

			int x = dl.front();

			dl.pop();

			for (int i = 1;i <= 52;i++)

				if (g[x][i]){

				 	g[x][i] = g[i][x] = 0;

				 	du[i]--;

				 	if (du[i] == 0){

				 	 	dl.push(i);

				 	}

				}

       }

       if (num!=0){

        	cout << "unbounded" << endl;

       }else{

        	cout << "bounded" << endl;

       }

	}

	return 0;

}

巴特西

【例题 6-19 UVA - 1572】Self-Assembly

最新文章

热门文章