看到题爽写dfs,怒得12分,求助
查看原帖
看到题爽写dfs,怒得12分,求助
1198866
yinY_楼主2024/3/6 23:58
import java.util.Scanner;

public class Main {
	static char[][] ar=new char[320][320];
	static int[][] judge=new int[320][320];
	static int[] fx= {-1,1,0,0};
	static int[] fy= {0,0,-1,1};
	static int n,m,stx,sty,count,total=99999;
	public static void main(String[] args) {
		Scanner inScanner=new Scanner(System.in);
		n=inScanner.nextInt();
		m=inScanner.nextInt();
		inScanner.nextLine();
		for (int i = 1; i <= n; i++) {
			String s1=inScanner.nextLine();
			for (int j = 1; j <=m; j++) {
				if (s1.charAt(j-1)=='@') {
					stx=i;
					sty=j;
				}
				ar[i][j]=s1.charAt(j-1);
			}
		}
		dfs(stx,sty);
		System.out.println(total);
	}
	private static void dfs(int x, int y) {
		// TODO Auto-generated method stub
		if (ar[x][y]=='#') {
			return;
		}
		for (char i='A'; i <='Z'; i++) {
			if (ar[x][y]==i) {
				ar[x][y]='.';
				find(i);
				ar[x][y]=i;
			}
		}
		if (ar[x][y]=='=') {
			total=Math.min(count, total);
			return;
		}
		for (int i = 0; i < 4; i++) {
			if (judge[x][y]==0) {
				count++;
				judge[x][y]=1;
				dfs(x+fx[i], y+fy[i]);
				count--;
				judge[x][y]=0;
			}
		}
	}
	private static void find(char ans) {
		// TODO Auto-generated method stub
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (ar[i][j]==ans) {
					ar[i][j]='.';
					dfs(i, j);
					ar[i][j]=ans;
				}
			}
		}
	}
}
2024/3/6 23:58
加载中...