War - uloha na cvičenia z PAZ1b

Created: 2008-06-19 - 16:58

Uloha pre Matiho - ti co su so mnou v skupine maju toto:
war 1 strana war 2 strana

Riesenie: Skusal som to pre ten testovaci vstup, takze by to malo byt spravne na 95%. Inac sa mi s tym nechcelo velmi babrat, takze moze byt, ze je tam nejaky bug... Byt na sutazi, tak to urcite este neposlem. Nastavovanie vztahov medzi vrcholmi som robil podobne ako pri Roy-Warshallovom algoritme na hladanie tranzitivneho uzaveru. Zlozitost tohto algoritmu je O(n^3) (n-pocet vrcholov), cize na sutazi by to aj tak zrejme neuspelo.

Edit: Prerobil som to tak, aby to fungovalo :D, lebo to prve riesenie bolo strasne :-). Teraz to pracuje s klasickym 2D polom a jednoduchymi oznaceniami. Predtym to fungovalo pre vstupy n<10 teraz to ide pre vstupy n<1000. Problem je ten, ze to nezbehne pre 10 000 ludi, pretoze nevie take velke pole inicializovat...



import java.util.*;

public class War {
	int[][] g;
	int pocetLudi;
	
	public War(){
		g = new int[1000][1000];
		for(int i=0;i<1000;i++)
			for(int j=0;j<1000;j++)
				g[i][j]=-1;
	}
	public void setEnemies(int x, int y){
		if(g[x][y]==-1){
			g[x][y]=0;
			g[y][x]=0;
			nastavVztahy();
		}
		else if(g[x][y]==1)
			System.out.println("-1");
	}
	public void setFriends(int x, int y){
		if(g[x][y]==-1){
			g[x][y]=1;
			g[y][x]=1;
			nastavVztahy();
		}
		else if(g[x][y]==0)
			System.out.println("-1");
	}
	public boolean areEnemies(int x, int y){
		if(g[x][y]==-1)
			return false;
		if(g[x][y]==0)
			return true;
		else
			return false;
	}
	public boolean areFriends(int x, int y){
		if(g[x][y]==-1)
			return false;
		if(g[x][y]==1)
			return true;
		else
			return false;
	}
	
	public void nastavVztahy(){
		for(int i=0;i<pocetLudi;i++){
			for(int j=0;j<pocetLudi;j++){
				for(int k=0;k<pocetLudi;k++){
					int x = i;
					int y = j;
					int z = k;
					if(g[x][y]!=-1 && g[y][z]!=-1){
						if(g[x][y]==0 && g[y][z]==1){
							if(g[x][z]==-1){
								g[x][z]=0;
								g[z][x]=0;
							}
						}
						else if(g[x][y]!=1 && g[y][z]!=0){
							if(g[x][z]==-1){
								g[x][z]=0;
								g[z][x]=0;
							}
						}
						else if(g[x][y]!=0 && g[y][z]!=0){
							if(g[x][z]==-1){
								g[x][z]=1;
								g[z][x]=1;
							}
						}
						else if(g[x][y]!=1 && g[y][z]!=1){
							if(g[x][z]==-1){
								g[x][z]=1;
								g[z][x]=1;
							}
						}
					}
				}
			}
		}
	}
	
	public String toString(){
		return g.toString();
	}
	
	
	
	public static void main(String[] args) {
		War vojna = new War();
		Scanner s = new Scanner(System.in);
		vojna.pocetLudi = s.nextInt();
		do{
			int x = s.nextInt();
			int y = s.nextInt();
			int z = s.nextInt();
			if(x==0 && y==0 && z==0)
				break;		
			else{
				switch (String.valueOf(x).charAt(0)) {
				case '1':
					vojna.setFriends(y,z);
					break;
				case '2':
					vojna.setEnemies(y,z);
					break;
				case '3':
					System.out.println(vojna.areFriends(y,z));
					break;
				case '4':
					System.out.println(vojna.areEnemies(y,z));
					break;
				default:
					break;
				}
			}
		}while(0==0);
	}
	/*
Testovaci vstup:
10
1 0 1
1 1 2
2 0 5
3 0 2
3 8 9
4 1 5
4 1 2
4 8 9
1 8 9
1 5 2
3 5 2
0 0 0
Testovaci vystup:
true
false
true
false
false
-1
false
	 */
}