Advertisement
Guest User

Untitled

a guest
Feb 13th, 2016
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.53 KB | None | 0 0
  1. package Algorithm;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.IOException;
  5. import java.io.InputStreamReader;
  6. import java.util.StringTokenizer;
  7.  
  8. class MySScanner {
  9. BufferedReader br;
  10. StringTokenizer st;
  11.  
  12. public MySScanner() {
  13. br = new BufferedReader(new InputStreamReader(System.in));
  14. }
  15.  
  16. String next() {
  17. while (st == null || !st.hasMoreElements()) {
  18. try {
  19. st = new StringTokenizer(br.readLine());
  20. } catch (IOException e) {
  21. e.printStackTrace();
  22. }
  23. }
  24. return st.nextToken();
  25. }
  26.  
  27. int nextInt() {
  28. return Integer.parseInt(next());
  29. }
  30.  
  31.  
  32. }
  33.  
  34. public class Main {
  35. //http:// www.spoj.com/problems/HPFORF/ HARRY POTTER AND THE FORBIDDEN FOREST
  36. boolean[][] flag;
  37. char[][] arr;
  38. int max;
  39. int[] value;
  40. int[][] dynamic;
  41.  
  42. public int wheretotraverse(int i, int j) {
  43. int sum = 0;
  44. if (i - 1 >= 0)
  45. sum += traverse(i - 1, j);
  46. if (j - 1 >= 0)
  47. sum += traverse(i, j - 1);
  48. if (i + 1 < arr.length)
  49. sum += traverse(i + 1, j);
  50. if (j + 1 < arr[0].length)
  51. sum += traverse(i, j + 1);
  52. return sum;
  53. }
  54.  
  55. public int traverse(int i, int j) {
  56. int out = 0;
  57. if (arr[i][j] == '*')
  58. out= 1;
  59. else {
  60. if (flag[i][j] != true) {
  61. flag[i][j] = true;
  62. out = wheretotraverse(i, j);
  63. }
  64. }
  65. dynamic[i][j]=max;
  66. return out;
  67. }
  68.  
  69. public static void main(String[] args) {
  70. MySScanner sScanner = new MySScanner();
  71. int max = sScanner.nextInt();
  72. int test = 0;
  73. Main hpforf=new Main();
  74. while (test<max){
  75. int n=sScanner.nextInt();
  76. int m=sScanner.nextInt();
  77. int innertest=sScanner.nextInt();
  78. hpforf.arr=new char[n][m];
  79. hpforf.value=new int[m*n];
  80. hpforf.dynamic=new int[n][m];
  81. hpforf.flag=new boolean[n][m];
  82. hpforf.max=2;
  83. for (int i=0;i<n;i++)
  84. hpforf.arr[i]=sScanner.next().toCharArray();
  85. for (int i=0;i<n;i++)
  86. for (int j=0;j<m;j++)
  87. {
  88. if(hpforf.arr[i][j]=='*'){
  89. hpforf.dynamic[i][j]=0;
  90. hpforf.value[0]=0;
  91. }else{
  92. if(hpforf.dynamic[i][j]==0){
  93. hpforf.value[hpforf.max]=hpforf.traverse(i,j);
  94. hpforf.max++;
  95. }
  96. }
  97. }
  98. for (int i=0;i<innertest;i++){
  99. int x=sScanner.nextInt()-1;
  100. int y=sScanner.nextInt()-1;
  101. System.out.println(hpforf.value[hpforf.dynamic[x][y]]);
  102. }
  103. test++;
  104. }
  105. }
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement