Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package Algorithm;
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.StringTokenizer;
- class MySScanner {
- BufferedReader br;
- StringTokenizer st;
- public MySScanner() {
- br = new BufferedReader(new InputStreamReader(System.in));
- }
- String next() {
- while (st == null || !st.hasMoreElements()) {
- try {
- st = new StringTokenizer(br.readLine());
- } catch (IOException e) {
- e.printStackTrace();
- }
- }
- return st.nextToken();
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- }
- public class Main {
- //http:// www.spoj.com/problems/HPFORF/ HARRY POTTER AND THE FORBIDDEN FOREST
- boolean[][] flag;
- char[][] arr;
- int max;
- int[] value;
- int[][] dynamic;
- public int wheretotraverse(int i, int j) {
- int sum = 0;
- if (i - 1 >= 0)
- sum += traverse(i - 1, j);
- if (j - 1 >= 0)
- sum += traverse(i, j - 1);
- if (i + 1 < arr.length)
- sum += traverse(i + 1, j);
- if (j + 1 < arr[0].length)
- sum += traverse(i, j + 1);
- return sum;
- }
- public int traverse(int i, int j) {
- int out = 0;
- if (arr[i][j] == '*')
- out= 1;
- else {
- if (flag[i][j] != true) {
- flag[i][j] = true;
- out = wheretotraverse(i, j);
- }
- }
- dynamic[i][j]=max;
- return out;
- }
- public static void main(String[] args) {
- MySScanner sScanner = new MySScanner();
- int max = sScanner.nextInt();
- int test = 0;
- Main hpforf=new Main();
- while (test<max){
- int n=sScanner.nextInt();
- int m=sScanner.nextInt();
- int innertest=sScanner.nextInt();
- hpforf.arr=new char[n][m];
- hpforf.value=new int[m*n];
- hpforf.dynamic=new int[n][m];
- hpforf.flag=new boolean[n][m];
- hpforf.max=2;
- for (int i=0;i<n;i++)
- hpforf.arr[i]=sScanner.next().toCharArray();
- for (int i=0;i<n;i++)
- for (int j=0;j<m;j++)
- {
- if(hpforf.arr[i][j]=='*'){
- hpforf.dynamic[i][j]=0;
- hpforf.value[0]=0;
- }else{
- if(hpforf.dynamic[i][j]==0){
- hpforf.value[hpforf.max]=hpforf.traverse(i,j);
- hpforf.max++;
- }
- }
- }
- for (int i=0;i<innertest;i++){
- int x=sScanner.nextInt()-1;
- int y=sScanner.nextInt()-1;
- System.out.println(hpforf.value[hpforf.dynamic[x][y]]);
- }
- test++;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement