OJ Board

Code: Select all

/*200*/
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;

char A[22],B[22],*a,*b;
int al[30][30], link[30],TS[30];
bool use[30];
priority_queue<int,vector<int>,greater<int> > q;
int amm;

void INITIAL()
{
     for (int i=0;i<26;i++)
     {
         al[i][0]=0;
         link[i]=0;
         use[i]=0;    
     }     
}
void LINK(char x,char y)
{
     use[y-'A']=true;
     use[x-'A']=true;
     link[y-'A']++;
     al[x-'A'][++al[x-'A'][0]]=y-'A';
}
void SCAN()
{
     scanf("%s",A);
     use[A[0]-'A']=true;
     a=A;b=B;
     while (scanf("%s",b)!=EOF)
     {
           if (b[0]=='#')break;
           int la=strlen(a),lb=strlen(b);
           for (int i=0;i<min(la,lb);i++)
           {
               if (a[i]==b[i])continue;
               LINK(a[i],b[i]);
               printf("1\n");
               break;
           }
           swap(a,b);
     }
}
void TOPOLOGICAL_SORT()
{
     amm=0;
     for (int i=0;i<26;i++)
     {
         if (use[i])
         {
            amm++;   
            if (link[i]==0)
            {
               q.push(i);    
            }
         }
     }
     int ptr=0;
     while (!q.empty())
     {
           int k=q.top();
           TS[ptr++]=k;
           q.pop();
           for (int i=1;i<=al[k][0];i++)
           {
               if (--link[al[k][i]]==0)
                  q.push(al[k][i]);  
           }
     }
}
int main()
{
    INITIAL();
    SCAN();
    TOPOLOGICAL_SORT();
    for (int i=0;i<amm;i++)
    {
        printf("%c",TS[i]+'A');    
    }
    puts("");
    //system ("pause");
    return 0;
}

Code: Select all

#include<iostream>
#include<string>

using namespace std;

int Min(string x,string y) {
    if(x.length()>y.length()) return (y.length());
    else return (x.length());
}


int main()
{
    int c=0;
    string s[25],f;
    char order[25];
    int check[27];

    while(1) {
        cin>>f;
        if(f=="#") break;
        s[c]=f;
        c++;
    }

    for(int i=0;i<27;i++) check[i]=0;

    order[0]=s[0][0];
    check[s[0][0]-'A']=1;
    int flag=0,index=1,j;


    for(int i=0;i<c-1;i++) {

        for(j=0;j<Min(s[i],s[i+1]);j++) {
            if(s[i][j]!=s[i+1][j] && check[s[i+1][j]-'A']==0) {
                flag=1;
                check[s[i+1][j]-'A']=1;
                order[index]=s[i+1][j];
                index++;
                break;
            }
        }
        if(flag==0) {
            for(int k=j;k<s[i+1].length();k++) {
                if(check[s[i+1][k]-'A']==0) {
                    order[index]=s[i+1][k];
                    check[s[i+1][j]-'A']=1;
                    index++;
                    flag=0;
                    break;
                }
            }
        }
    }
    for(int i=0;i<index;i++){
        cout<<order[i];
    }
    cout<<endl;
    return 0;
}

Code: Select all

AC :D

Code: Select all

#include<stdio.h>

#define SIZE 22

int input[10000][SIZE], ruleArray[26][26];

char inputCh;
int inputInt;

int colorArray[102];
int inputArray[26], outputArray[26], visited[26];

int count;

bool didResultComputed;



void bin (int level)
{
	if (level==count )
	{
		for (int i =0; i< count; i++)
		{
			printf("%c", (90-outputArray[i]));
		}
		//printf("\n");

		didResultComputed = true;
		return;
	}

	for (int i =0; i< count; i++)
	{
		if (visited[i]==0 && didResultComputed==false)
		{
			for (int j = 0; j < count; j++)
			{
				if (ruleArray[i][j] == 1 && visited[j] == 1)
				return ;								
			}
			outputArray[level] = inputArray[i];
			visited[i]=1;
			bin(level+1);
			visited[i]=0;
		}
	}

}


void printInputArray(int count)
{
	printf("\nInput Array: \n");
	printf("count: %d \n", count);
	for (int i =0; i<count; i++)
	{
		printf("%d ", inputArray[i]);
	}

		printf("\n");
}


void printRuleArray()
{
	for (int i =0 ; i <26; i++)
	{
		for (int j =0 ; j <26; j++)
		{
			printf("%d ", ruleArray[i][j]);
		}
		printf("\n");
	}
}


int getAbs(int value)
{
	if (value<0)
		return value * -1;
	else
		return value;

}

void createRuleArray (int m, int n)
{
	int index1 = 0, index2 = 0;
	for (int i = 0; i < m; i++)
	{
		for(int j = 0; i<n;i++)
		{
			if (i+1<m && j+1<n && input[i][j] !=0 && input[i+1][j]!=0)
			{
				if (input[i][j] != input[i+1][j])
				{
					index1 = getAbs(90-input[i][j]);
					index2 = getAbs(90-input[i+1][j]);
					ruleArray[index1][index2] = 1;

					//printf("index1: %d index2: %d ruleArray[%d][%d]: %d \n", index1, index2, index1, index2, ruleArray[i][j]);

					i++;
				}
				else if (input[i][j] == input[i+1][j])
				{
					//j++;
				}
				else
				{
					continue;
				}
			}
		}
	}
}


void printInputArray(int m, int n)
{
	//printf ("m: %d n: %d", m,n);

	for(int i =0 ; i<m;  i++)
		{
			for (int j=0; j <n; j++)
			{
				printf("%d ", input[i][j]);
			}
			printf("\n");
		}
}


int main()
{
	int m =0, n =0;

	while((inputCh=getchar())!='#')
	{
		
		inputInt = inputCh;

		if(inputInt == 10)
		{
			//printf("\n");
			m++;
			n = 0;
			continue;
		}
		if (inputInt>= 65 && inputInt <= 90)
		{

			input[m][n]= inputInt;
			colorArray[getAbs(90-inputInt)] = 1;
			n++;
		}
	}

	count=0;
	for(int i =0; i<100; i++)
	{
		if(colorArray[i]==1)
		{
			
			inputArray[count]=i;
			count++;
			
		}
	}
	
	//debug 
	//printInputArray(count);
	//debug
	//printInputArray(m, SIZE);
	
	createRuleArray(m, SIZE);

	//debug
	//printRuleArray();

	didResultComputed = false;
	bin (0);
	return 0;
}