Register
|
Login
Home
News
Competitions
Practice
How to
Rankings
Calendar
Arena
CodeFu 2007
CodeFu'07 Highlights
Jazoon'07 Highlights
Schedule
Rules
Prizes
Results
Competitions
»
Main CodeFu Competitons
»
CodeFu 2007
»
Results
CodeFu 2007 Results
CodeFu Final Round Results
toroman's solution for 500: NewsFlow, written in Java
public class NewsFlow { public int minutes(String[] willing) { int len = willing.length; boolean[] spoken = new boolean[len]; boolean[][] speaks = new boolean[len][len]; int[][] dist = new int[len][len]; for (int i=0; i<len; i++) for (int j=0; j<len; j++) { speaks[i][j] = willing[i].charAt(j) == 'Y'; dist[i][j] = speaks[i][j] ? 1 : Integer.MAX_VALUE; } spoken[0] = true; for (int m=0; m<len; m++) for (int i=0; i<len; i++) for (int j=0; j<len; j++) if (dist[i][m] < Integer.MAX_VALUE && dist[m][j] < Integer.MAX_VALUE) dist[i][j] = Math.min(dist[i][j], dist[i][m] + dist[m][j]); int time = 0; Loop: while (true) { time++; boolean did = false; for (int i=0; i<len; i++) { if (spoken[i]) { int maxd = -1; int maxi = -1; for (int j=0; j<len; j++) if (i != j && !spoken[j] && dist[i][j] > maxd && dist[i][j] < Integer.MAX_VALUE) { maxd = dist[i][j]; maxi = j; } if (maxi > -1) { did = true; spoken[maxi] = true; } } } if (!did) break; for (int i=0; i<len; i++) if (!spoken[i]) continue Loop; break; } return time; } // public static void main(String[] args) { // NewsFlow n = new NewsFlow(); // String[] c1 = {"NYNN","NNYN","NNNY","NNNN"}; // System.out.println(n.minutes(c1)); // } }