赞
踩
import java.util.*; public class Meituan { static int m,n; public static void main(String[] args) { Scanner in = new Scanner(System.in); m = in.nextInt(); n = in.nextInt(); char[][]cs=new char[m][n]; for(int i=0;i<m;i++){ String s=in.next(); for(int j=0;j<n;j++){ cs[i][j]=s.charAt(j); } } mp.put('A','B'); mp.put('B','C'); mp.put('C','D'); mp.put('D','E'); mp.put('E','A'); mp.put('#','F'); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(cs[i][j]=='A'){ cnt=0; mark=new boolean[m][n]; dfs(cs,i,j); } if(f){ System.out.println(-1); return; } } } System.out.println(ans); } static int ans=0; static int[]dirs=new int[]{-1,0,1,0,-1}; static int cnt=0; static Map<Character,Character>mp=new HashMap<>(); static boolean[][]mark=new boolean[m][n]; static boolean f=false; static void dfs(char[][]cs, int p, int q){ if(f){ return; } for(int i=0;i<4;i++){ int nx=p+dirs[i]; int ny=q+dirs[i+1]; if(nx>=0&&nx<m&&ny>=0&&ny<n){ if(cs[nx][ny]==mp.get(cs[p][q])){ if(mark[nx][ny]){ f=true; return; } mark[nx][ny]=true; cnt++; ans=Math.max(ans,cnt); dfs(cs, nx,ny); cnt--; } } } } }
case1:结果-1
2 5
ABCDE
EDCBA
case2:结果2
3 3
ABC
BEE
CEE
case2:正确结果28
7
1 1 1 2 2 2 3
1 2
1 3
2 4
2 5
3 6
3 7
2
2 4
3 5
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { static List<List<Integer>>list=new ArrayList<>(); static int[]weight; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); weight=new int[n]; isColor=new int[n]; for(int i=0;i<n;i++){ int w = in.nextInt(); weight[i]=w; } for(int i=0;i<n;i++){ list.add(new ArrayList<>()); } for(int i=0;i<n-1;i++){ int a = in.nextInt()-1; int b = in.nextInt()-1; // System.out.println("a:"+a+",b:"+b); list.get(a).add(b); } int q=in.nextInt(); for(int i=0;i<q;i++){ int u=in.nextInt()-1; int x=in.nextInt(); if(isColor[u]!=x) paint(u,x); } dfs(0); System.out.println(res); } static long res=0; static int[]isColor; static void dfs(int u){ res+=weight[u]; List<Integer>tmp=list.get(u); for(int i=0;i<tmp.size();i++){ dfs(tmp.get(i)); } } static void paint(int u,int x){ weight[u]=x; isColor[u]=x; List<Integer>tmp=list.get(u); for(int i=0;i<tmp.size();i++){ paint(tmp.get(i),x); } } }
你的解决方法主要利用了深度优先搜索(DFS)和递归的思想。通过DFS遍历树的每个节点,并在遍历的过程中进行计算和状态更新。你还使用了一个时间戳的机制来记录每个节点最后一次被涂色的时间,以及使用了传递状态的方法来在递归调用中传递信息。
import java.util.*; public class Meituan { // 记录各个节点的子节点 static List<List<Integer>>list=new ArrayList<>(); // 记录权重以及特色时间戳 static long[][]paintTime; // result static long res=0; // 节点数 static int n; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); paintTime=new long[n][2]; for(int i=0;i<n;i++){ int w = in.nextInt(); paintTime[i][1]=w; } for(int i=0;i<n;i++){ list.add(new ArrayList<>()); } for(int i=0;i<n-1;i++){ int a = in.nextInt()-1; int b = in.nextInt()-1; list.get(a).add(b); } int q=in.nextInt(); for(int i=0;i<q;i++){ int u=in.nextInt()-1; // 节点 int x=in.nextInt(); // 涂色值 long timeStamp= System.currentTimeMillis(); paintTime[u][0]=timeStamp; paintTime[u][1]=x; } sumDfs(0,paintTime[0][0],paintTime[0][1]); System.out.println(res); } static void sumDfs(int u, long timeStamp, long x){ // 获取最新的被涂色的值 long finalX=timeStamp>paintTime[u][0]?x:paintTime[u][1]; long finalTimeStamp=Math.max(timeStamp,paintTime[u][0]); res+=finalX; List<Integer>tmp=list.get(u); for (int i = 0; i < tmp.size(); i++) { sumDfs(tmp.get(i),finalTimeStamp,finalX); } } }
小美拿到了两个长度为n的字符串a和b,她希望生成一个新的长度为n的字符串c,希望满足ci是从ai和bi中二选一生成的。小美想知道,最终可以生成的所有字符串中有多少种不同的回文串。由于答案过大,请对10^9+7取模。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。