Competitions » Main CodeFu Competitons » CodeFu 2007 » Results
CodeFu 2007 Results

CodeFu Final Round Results

sqrt_x's solution for 500: NewsFlow, written in Java

import java.util.LinkedList;

public class NewsFlow {
  public int minutes(String[] willing)
	{
		int n = willing.length;
		int[][] w = new int[n][n];
		
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
			{
				if (willing[i].charAt(j) == 'Y')
					w[i][j] = 1;
				else
					w[i][j] = 0;
			}
		
		int[] time = new int[n];
		int[] from = new int[n];
		//int v = 0;
		//LinkedList<Pair> queue = new LinkedList<Pair>();
		//Stack<Pair> stack = new Stack<Pair>();
		LinkedList<Integer> queue = new LinkedList<Integer>();
		
		queue.addLast(new Integer(0));
		//int total = 1;
		int curr;
		int min = 100;
		int mint = 0, od = 0;
		boolean changed = true;
		while (changed)
		{	
			changed = false;
			min = 100;
			for (int i = 0; i < queue.size(); i++)
			{
/*
				for (int k = 0; k < n; k++)
					System.out.println(time[k]);
				System.out.println();
*/
				
				curr = queue.get(i).intValue();
				//System.out.println(queue.toString());
				for (int j = 1; j < n; j++)
					if ((j != curr) && (w[curr][j] > 0))
						if ((time[j] == 0) || (from[curr] + 1 < time[j]))
							if (from[curr] + 1 < min)
						{
							/*
							queue.addLast(new Integer(j));
							time[j] = from[curr] + 1;
							from[j] = time[j];
							from[curr]++;
							changed = true;
							*/
							changed = true;
							min = from[curr] + 1;
							mint = j;
							od = curr;
						}
				
				
			}
			
			if (changed)
			{
				queue.addLast(new Integer(mint));
				time[mint] = min;
				from[mint] = time[mint];
				from[od]++;
			}
		}
		
		
		int max = -1;
		
		for (int i = 1; i < n; i++)
		{
			if (time[i] > max)
				max = time[i];
			if (time[i] == 0)
			{
				max = -1;
				break;
			}
		}
		
		return max;
	}
}