Advertisement
Guest User

Untitled

a guest
Mar 25th, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.75 KB | None | 0 0
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. public class Mars {
  6. public static void (String[] args) {
  7. int n,i,j;
  8. boolean a;
  9. n = in.nextInt();
  10. boolean [][] array = new boolean[n][n];
  11. boolean [] connect = new boolean[n];
  12. int [] result = new int[n];
  13. int [] temp = new int[n];
  14. int first,last;
  15. Scanner sc = new Scanner(System.in);
  16. String s;
  17. for (i=0;i<n;i++) {
  18. s = sc.nextLine();
  19. char [] myCharArray = s.toCharArray ();
  20. for (j=0;j<n;j++) {
  21. if (myCharArray[j]=='+') array[i][j] = false;
  22. else array[i][j] = true;
  23. }
  24. }
  25. a = res(-1,n);
  26. }
  27. if (a || (last < n+1)) {
  28. if (last < first) {
  29. int[] result = (int[])tmp.clone();
  30. first=last;
  31. }
  32. for (int i=0; i <= first; i++)
  33. System.out.println(result[i]+" ");
  34. }
  35. else System.out.println("No solution");
  36.  
  37.  
  38. public boolean res(int a, int n) {
  39. for (i=a+1;i<n;i++) {
  40. if (check_con(i,first) {
  41. first++;
  42. result[first] = i;
  43. connect[i]=true;
  44. if (res(i,n))
  45. return true;
  46. first--;
  47. connect[i]=false;
  48. }
  49. }
  50. if (check(n)) {
  51. int[] tmp = (int[])result.clone();
  52. if (last > first) last = first;
  53. }
  54. if (first == n/2 - 1) {
  55. if (check(n))
  56. return true
  57. }
  58. return false;
  59. }
  60.  
  61. public boolean check_con(int a, int first) {
  62. int i;
  63. for (i=0;i<=first;i++) {
  64. if (!arry[a][result[i]-1])
  65. return false;
  66. }
  67. return true;
  68. }
  69.  
  70. public boolean check(int n) {
  71. int i,j;
  72. for (i= 0;i<n-1;i++) {
  73. if (connect[i]) {
  74. for (j=i+1;j<n;j++)
  75. if (!is_connect[j] && !array[i][j])
  76. return false;
  77. }
  78. }
  79. return true;
  80. }
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement