Let $$$dp[i][j$$$] be the number of dress patterns where $$$i, j$$$ is the bottom-most vertex.

Then, $$$dp[i][j] = 1 + min (dp[i - 1][j - 1], dp[i - 1][j + 1], dp[i - 2][j])$$$. 1 is added at the beginning as it is the case that the point $$$i, j$$$ is a solution, and min() is the furthest the pattern exists in the right, top, and left directions.

Note that $$$2 <= i < n$$$ and $$$1 <= j < n-1$$$.

Let's define the one-square pattern as a size $$$1$$$ pattern, the five-square pattern as a size $$$2$$$ pattern, and so on.

Now, let's consider patterns that are centered at each cell individually. Note that if a pattern of size $$$n$$$ centered at a cell $$$(a, b)$$$ exists, then every single pattern of size $$$1$$$ to $$$n-1$$$ centered at a cell $$$(a, b)$$$ also exists. Therefore, to count all the patterns, it suffices to calculate the largest pattern centered at each cell.

Next, note that a pattern of size $$$n$$$ centered at $$$(a, b)$$$ contains all the cells that are a Manhattan distance of $$$n-1$$$ or less away from $$$(a, b)$$$. So, in order for a pattern of size $$$n$$$ to exist at $$$(a, b)$$$, every single cell that is a Manhattan distance of $$$n-1$$$ or less away from $$$(a, b)$$$ must be the same color as $$$(a, b)$$$. This means that, for a cell $$$(a, b)$$$, the size of the largest pattern that is centered at that cell is equal to the smallest Manhattan distance between $$$(a, b)$$$ and any cell that is not the same color as $$$(a, b)$$$.

We can use a multi-source BFS to calculate this value for all the cells. Let's define a "boundary" cell as a cell that is either on the edge of the grid or that is not surrounded on all four sides by cells of the same color. These cells all have values of $$$1$$$. We then just BFS from all the "boundary" cells and update the values for all the remaining cells. The sum of all the values is the answer.

My solution (Java)

(Since the TL was 1 second, I had to make several optimizations to make the BFS run in time. I eventually ended up using an array with two pointers as my queue, which made it work.)

    import java.io.*;
    import java.util.*;
    public class chesss {
        public static void main(String[] args) throws Exception{
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter writer = new PrintWriter(System.out);
            int t = Integer.parseInt(in.readLine());
            for(int i = 0; i < t; i++){
                int size = Integer.parseInt(in.readLine());
                if(size % 2 == 0){
                    writer.println(size - (size/2 - 1));
                }
                else{
                    writer.println(size - ((size - 1)/2));
                }
            }
            writer.close();
            in.close();
        }
    }

    import java.io.*;
    import java.util.*;
    public class building {
        public static void main(String[] args) throws Exception{
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter writer = new PrintWriter(System.out);
            int n = Integer.parseInt(in.readLine());
            StringTokenizer st = new StringTokenizer(in.readLine());
            TreeMap<Integer, Integer> sizes = new TreeMap<>();
            for(int i = 0; i < n; i++){
                int length = Integer.parseInt(st.nextToken());
                if(!sizes.containsKey(length)){
                    sizes.put(length, 1);
                }
                else{
                    sizes.put(length, sizes.get(length) + 1);
                }
            }
            TreeSet<Integer> pair = new TreeSet<>(), quad = new TreeSet<>(), many = new TreeSet<>();
            for(int i: sizes.keySet()){
                if(sizes.get(i) > 1 && sizes.get(i) < 4){
                    pair.add(i);
                }
                else if(sizes.get(i) > 1 && sizes.get(i) < 8){
                    pair.add(i); quad.add(i);
                }
                else if(sizes.get(i) > 7){
                    pair.add(i); quad.add(i); many.add(i);
                }
            }
            int q = Integer.parseInt(in.readLine());
            for(int i = 0; i < q; i++){
                st = new StringTokenizer(in.readLine());
                char type = st.nextToken().charAt(0);
                int amount = Integer.parseInt(st.nextToken());
                if(type == '+'){
                    if(!sizes.containsKey(amount)){
                        sizes.put(amount, 1);
                    }
                    else{
                        sizes.put(amount, sizes.get(amount) + 1);
                        if(sizes.get(amount) > 1 && sizes.get(amount) < 4){
                            pair.add(amount);
                        }
                        else if(sizes.get(amount) > 1 && sizes.get(amount) < 8){
                            pair.add(amount); quad.add(amount);
                        }
                        else if(sizes.get(amount) > 7){
                            pair.add(amount); quad.add(amount); many.add(amount);
                        }
                    }
                }
                else{
                    if(sizes.get(amount) == 1){
                        sizes.remove(amount);
                        pair.remove(amount); quad.remove(amount); many.remove(amount);
                    }
                    else if(sizes.get(amount) == 2){
                        pair.remove(amount); quad.remove(amount); many.remove(amount);
                        sizes.put(amount, sizes.get(amount) - 1);
                    }
                    else if(sizes.get(amount) == 4){
                        quad.remove(amount); many.remove(amount);
                        sizes.put(amount, sizes.get(amount) - 1);
                    }
                    else if(sizes.get(amount) == 8){
                        many.remove(amount);
                        sizes.put(amount, sizes.get(amount) - 1);
     
                    }
                    else{
                        sizes.put(amount, sizes.get(amount) - 1);
                    }
                }
                if(many.size() > 0){
                    System.out.println("YES");
                    continue;
                }
                if(quad.size() > 1){
                    System.out.println("YES");
                    continue;
                }
                if(quad.size() == 1){
                    int num = sizes.get(quad.first());
                    if(num - 4 < 2 && pair.size() > 2){
                        System.out.println("YES");
                        continue;
                    }
                    if(num - 4 > 1 && pair.size() > 1){
                        System.out.println("YES");
                        continue;
                    }
                }
                System.out.println("NO");
            }
            writer.close();
        }
    }

    import java.io.*;
    import java.util.*;
    public class pinkiePie {
        static TreeMap<Integer, TreeSet<Integer>> templ = new TreeMap<>(new sort1());
        public static void main(String[] args) throws Exception{
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            int t = Integer.parseInt(in.readLine());
            for(int i = 0; i < t; i++){
                templ.clear();
                int n = Integer.parseInt(in.readLine());
                int[] arr = new int[n];
                StringTokenizer st = new StringTokenizer(in.readLine());
                List<occ> occs = new ArrayList<>();
                for(int j = 0; j < n; j++){
                    arr[j] = Integer.parseInt(st.nextToken());
                }
                Arrays.sort(arr);
                for(int j = 0; j < n; j++){
                    int index = j, cnt = 0;
                    while(index < n && arr[index] == arr[j]){
                        index++;
                        cnt++;
                    }
                    j = index - 1;
                    occs.add(new occ(arr[j], cnt));
                }
                for(occ j: occs){
                    TreeSet<Integer> put;
                    if(!templ.containsKey(j.occurrences)){
                        put = new TreeSet<>();
                    }
                    else{
                        put = templ.get(j.occurrences);
                    }
                    put.add(j.num);
                    templ.put(j.occurrences, put);
                }
                occs.sort(new sort());
                System.out.println(solve(occs, n));
            }
        }
        static int solve(List<occ> occs, int n){
            int ans = 0;
            int lb = 0, ub = n;
            while(lb != ub){
                int m = (lb + ub)/2;
                if(good(occs, n, m)){
                    lb = m + 1;
                    ans = Math.max(ans, m);
                }
                else{
                    ub = m;
                }
            }
            return ans;
        }
        static boolean good(List<occ> occs, int n, int gap){
            TreeMap<Integer, TreeSet<Integer>> map = new TreeMap<>(new sort1());
            for(int i: templ.keySet()){
                TreeSet<Integer> put = new TreeSet<>(templ.get(i));
                map.put(i, put);
            }
            Queue<occ> unusable = new LinkedList<>();
            int[] fill = new int[n];
            for(int i = 0; i < gap; i++){
                if(map.isEmpty()){
                    return false;
                }
                fill[i] = map.get(map.firstKey()).first();
                unusable.add(new occ(map.get(map.firstKey()).first(), map.firstKey()));
                map.get(map.firstKey()).remove(map.get(map.firstKey()).first());
                if(map.get(map.firstKey()).size() == 0){
                    map.remove(map.firstKey());
                }
            }
            for(int i = gap; i < n; i++){
                if(map.isEmpty()){
                    return false;
                }
                fill[i] = map.get(map.firstKey()).first();
                occ addBack = unusable.poll();
                unusable.add(new occ(map.get(map.firstKey()).first(), map.firstKey()));
                map.get(map.firstKey()).remove(map.get(map.firstKey()).first());
                if(map.get(map.firstKey()).size() == 0){
                    map.remove(map.firstKey());
                }
                if(addBack != null && addBack.occurrences > 1){
                    //add the latest unusable occ into the map
                    if(map.containsKey(addBack.occurrences - 1)){
                        map.get(addBack.occurrences - 1).add(addBack.num);
                    }
                    else{
                        TreeSet<Integer> put = new TreeSet<>();
                        put.add(addBack.num);
                        map.put(addBack.occurrences - 1, put);
                    }
                }
            }
            return true;
        }
    }
     
    class occ implements Comparable<occ>{
        int num, occurrences;
        public occ(int num, int occurrences){
            this.num = num; this.occurrences = occurrences;
        }
        public int compareTo(occ other){
            return other.num - this.num;
        }
    }
     
    class sort implements Comparator<occ>{
        public int compare(occ a, occ b){
            return b.occurrences - a.occurrences;
        }
    }
     
    class sort1 implements Comparator<Integer>{
        public int compare(Integer a, Integer b){
            return b - a;
        }
    }