ZOJ 2193 Window Pains AOV网络

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1193

 

结题报告：本次代码写的比较乱，但是感觉收获还是不小的

第一次完全靠自己手写邻接表，虽然调了两天，但是最终还是搞出来了

首先4*4方格中每个方格可能出现的数字

1	1，2	2，3	3
1，4	1，2，4，5	2，3，5，6	3 ，6
4，7	4，5，7，8	5，6，8，9	6，9
7	7，8	8，9	9

输入的数字就是位于最上面的数字，然后与下面的数字都有关系，这种关系用邻接表存储

最后用拓扑排序，如果不存在环的话，就证明系统没有崩溃

 

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<string>

using namespace std;

struct node
{
	int to;
	struct node *next;
};

node *List[10];
stack<int>S;
int mp[5][5],vis[10];
int counts[10];
int output[10];
string a[4][4]={
"1","12","23","3", "14","1245","2356","36",
"47","4578","5689","69", "7","78","89","9" };


void CreatNet( )
{
	int len = 0;
	int flag = 0;
	for( int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			memset(vis,0,sizeof(vis));
			len = a[i][j].length( );
			for(int t= 0;t<len;t++)
			{
				flag = 0;
				node *pre = new node; 
				node *temp = new node;
				int cnt = a[i][j][t]-'0';
				if(mp[i][j] == cnt) continue;
				else
				{
					temp->to = cnt;
					
					temp->next = NULL; 
				}
				if(List[mp[i][j]]==NULL)
				{
					List[mp[i][j]] = temp;
					counts[cnt]++;
				}
				else
				{
					pre = List[mp[i][j]];
				
					while(pre->next != NULL)
					{
						if(pre->to == temp->to ) { flag = 1; break; }
						pre = pre->next ;
					}
					if(!flag)
					{
						temp -> next = List[mp[i][j]];
						List[mp[i][j]] = temp;
						counts[cnt]++;
					}
				}
			}
		}
	} 
}

void TopoSort()
{
	int pos,cnt = 0;
	for(int i=1;i<=9;i++)
	{
		if( counts[i] == 0)
			S.push(i);
	}
	while(!S.empty())
	{
		pos = S.top();
		S.pop();
		output[cnt++] = pos;
		node *temp = new node;
		temp = List[pos];
		while(temp != NULL )
		{//	printf("%d. ",temp->to );
			counts[temp->to]--;
			if(counts[temp->to] == 0)
			{
				S.push(temp->to);
			}
			temp = temp->next;
		}
	}
}

int main( )
{
	char str1[10],str2[10],str[10];
	while(scanf("%s",str1) != EOF)
	{
		int i,j=0;
		memset(List,0,sizeof(List));
		memset(counts,0,sizeof(counts));
		memset(output,0,sizeof(output));
		if(strcmp(str1,"ENDOFINPUT")==0) break;
		for(i=0;i<4;i++)
		{
			for(int j=0;j<4;j++)
			{
				scanf("%d",&mp[i][j]);
			}
		}
		scanf("%s",str2);
		CreatNet( );
	//	for(int i=1;i<=9;i++)
	//	{
	//		printf("%d, ",counts[i]);
	//	}
	//	printf("\n");
		TopoSort( );
		//printf("\n");
		bool flag = false;
		for(int i=0;i<9;i++)
		{
			if(output[i] == 0)
			{
				flag = true;
				break;
			} 
			//printf("%d, ",output[i]);
		}
		if(!flag) printf("THESE WINDOWS ARE CLEAN");
		else printf("THESE WINDOWS ARE BROKEN");
		printf("\n");
	}
	return 0;
}