Uva_Problems/Uva11906.java at master · mostafamt/Uva_Problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.util.* ;
import java.io.* ;
/**
 * 11906 - Knight in a War Grid
 * @author mostafa
 */
public class Uva11906
{
    static boolean [][] blocked ;
    static boolean [][] visited ;
    static boolean [][] tmpVisit ;
    static int R , C , M , N  , even , odd ;
    static int [] dx ;
    static int [] dy ;

    static void dfs(int i , int j)
    {
        visited[i][j] = true ;
        int sum = 0 ;
        for (int k = 0; k < 8 ; k++)
        {
            int x = i+dx[k];
            int y = j+dy[k];
            if(isValid(x,y) && !tmpVisit[x][y])
            {
                sum++ ;
                tmpVisit[x][y] = true ;
            }
        }
        for (int k = 0; k < 8 ; k++) {
            int x = i+dx[k];
            int y = j+dy[k];
            if(isValid(x,y) && tmpVisit[x][y])
            {
                tmpVisit[x][y] = false ;
            }
        }

        if(sum%2==0) even++;
        else         odd++ ;

        for (int k = 0; k < 8 ; k++)
            if(isValid(i+dx[k], j+dy[k]))
            {
                if(!visited[i+dx[k]][j+dy[k]])
                    dfs(i+dx[k], j+dy[k]);
            }
    }

    static boolean isValid(int i , int j)
    {
        if(i < 0 || j < 0 || i >= R || j >= C || blocked[i][j])
            return false ;
        return true ;
    }

    public static void main(String[] args) throws IOException
    {
        Scanner sc = new Scanner(System.in);
        PrintWriter pr = new PrintWriter(System.out);
        StringBuilder sb = new StringBuilder();
        int tc = sc.nextInt();
        for(int t = 1 ; t <= tc ; t++)
        {
            R = sc.nextInt();
            C = sc.nextInt();
            M = sc.nextInt();
            N = sc.nextInt();
            int w = sc.nextInt();
            blocked = new boolean[R][C];
            visited = new boolean [R][C];
            tmpVisit = new boolean [R][C];
            dx = new int[]{ M , M , -M , -M , N ,  N , -N , -N };
            dy = new int[]{ N , -N , N , -N , M , -M ,  M , -M };
            while(w-->0)
                blocked[sc.nextInt()][sc.nextInt()] = true ;
            even = odd = 0 ;
            dfs(0, 0);
            sb.append("Case ").append(t).append(": ").append(even).append(" ").append(odd).append("\n");
        }
        pr.print(sb.toString());
        sc.close();
        pr.close();
    }

}