提示

对于40%的数据，2<=N<=11

对于100%的数据，2<=N<=18

题解思路

1.暴力dfs会爆栈。
2.使用首位分别dfs，一条从(0，0)向右下开始，一条从(n-1,n-1)想左上开始。
3.(dfs1)当其x，y坐标相加等于n-1时，即已经走完了一半的路径，此时将路径字符串放入下标为当前x的set数组中。
  同时将路径字符串存入map中，计数为1.
 4.dfs2同理，此时只需要拿着从(n-1,n-1)走过来的字符串和从头走过来的字符串相互比较，如果终点相同且路径
 字符串相同，则ans++。

暴力dfs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
//纯dfs只能得10分
public class Main {
    static int[] dx= {0,1};
    static int[] dy= {1,0};
    static int n;
    static int N=20;
    static int ans=0;
    static String[][] g=new String[N][N];
    static HashSet<String> set=new HashSet<String>();
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(reader.readLine().trim());
        for(int i=0;i<n;i++) {
            g[i]=reader.readLine().split("");
        }
        dfs(0,0,g[0][0]);
        for(String s1:set) {
            StringBuilder sb=new StringBuilder(s1);
            String s2=sb.reverse().toString();
            if(s1.equals(s2)) {
                ans++;
            }
        }
        System.out.println(ans);
    }

    private static void dfs(int x, int y,String path) {
        if(x==n-1&&y==n-1) {
            set.add(path);
            return ;
        }
        for(int i=0;i<2;i++) {
            int tx=x+dx[i];
            int ty=y+dy[i];
            if(check(tx,ty)) {
                dfs(tx,ty,path+g[tx][ty]);
            }
        }
    }

    private static boolean check(int tx, int ty) {
        // TODO Auto-generated method stub
        if(tx>=0&&tx<n&&ty>=0&&ty<n) return true;
        return false;
    }
}

优化代码

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.HashSet;

public class Main {
    static int n;
    static int N=20;
    static char[][] g=new char[N][N];
    static HashSet<String>[] set=new HashSet[N];
    static HashMap<String,Integer> map=new  HashMap<String,Integer>();
    static int[] dx= {1,0,-1,0};
    static int[] dy= {0,1,0,-1};
    static int ans=0;
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer=new BufferedWriter(new OutputStreamWriter(System.out));
        n=Integer.parseInt(reader.readLine());
        for(int i=0;i<N;i++) {
            set[i]=new HashSet<String>();
        }
        for(int i=0;i<n;i++) {
            g[i]=reader.readLine().toCharArray();
        }
        dfs1(0,0,"");
        dfs2(n-1,n-1,"");
        writer.write(ans+"\n");
        writer.flush();
    }
    private static void dfs2(int x, int y, String str) {
        // TODO Auto-generated method stub
        if(x<0||y<0) return ;
        str+=g[x][y];
        if(x+y==n-1) {
            if(set[x].contains(str)&&map.get(str)!=0) {
                set[x].remove(str);
                map.put(str,0);
                ans++;
            }
            return;
        }
        for(int i=2;i<4;i++) {
            dfs2(x+dx[i],y+dy[i],str);
        }
    }
    private static void dfs1(int x, int y, String str) {
        // TODO Auto-generated method stub
        if(x>=n||y>=n) return;
        str+=g[x][y];
        if(x+y==n-1) {
            set[x].add(str);
            //同样的字符串只需处理一次,所以覆盖赋值也为1
            map.put(str, 1);
            return ;
        }
        for(int i=0;i<2;i++) {
            dfs1(x+dx[i],y+dy[i],str);
        }
    }
}

set+set

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    static int[] dx= {0,1};
    static int[] dy= {1,0};
    static int ans;
    static int n;
    static int N=20;
    static String[][] g=new String[N][N];
    static HashSet[] set=new HashSet[N];
    static HashSet<String> path=new HashSet<String>();
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(reader.readLine().trim());
        for(int i=0;i<n;i++) {
            g[i]=reader.readLine().split("");
        }
        for(int i=0;i<n;i++) {
            set[i]=new HashSet<String>();
        }
        dfs1(0,0,g[0][0]);
        dfs2(n-1,n-1,g[n-1][n-1]);
        System.out.println(ans);
    }
    private static void dfs2(int x, int y,String str) {
        // TODO Auto-generated method stub
        if(x+y==n-1) {
            if(set[x].contains(str)&&path.contains(str)) {
                path.remove(str);
                ans++;
            }
            return;
        }
        for(int i=0;i<2;i++) {
            int tx=x-dx[i];
            int ty=y-dy[i];
            String temp=str+g[tx][ty];
            dfs2(tx,ty,temp);
        }
    }
    private static void dfs1(int x,int y,String str) {
        // TODO Auto-generated method stub
        if(x+y==n-1) {
            set[x].add(str);
            path.add(str);

            return;
        }
        for(int i=0;i<2;i++) {
            int tx=x+dx[i];
            int ty=y+dy[i];
            String temp=str+g[tx][ty];
            dfs1(tx,ty,temp);

        }
    }
}