求更优dfs剪枝方案

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,f[101][101],dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
char a[101][101];
void dfs(int x,int y,int step)
{
	if(x==n&&m==y)
	{
		ans=min(ans,step);
		return;
	}
	if(a[x][y]=='x')step++; 
	for(int i=0;i<4;i++)
	{
		int nx=x+dir[i][0],ny=y+dir[i][1];
		if(nx>n||ny>m||nx<1||ny<1||a[nx][ny]=='1'||step+1>=f[nx][ny])continue;
		if(a[nx][ny]>='A'&&a[nx][ny]<='z')
		{
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=m;j++)
				{
					if(a[i][j]==a[nx][ny])
					{
						if(i==nx&&ny==j)break;
						else f[nx][ny]=step+1,dfs(i,j,step+1);
					}
				}
			}
		}
		else 
		{
			f[nx][ny]=step+1; 
			dfs(nx,ny,step+1);
		}
	}
}
int main()
{
    cin>>n>>m;
    memset(f,0x3f,sizeof(f)); 
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
    	{
    		cin>>a[i][j];
		}
	}
	ans=2147483647;
	dfs(1,1,0);
	if(ans==2147483647)cout<<"NO Solution.";
	else cout<<ans;
    return 0; 
}