DAY53-图论BFS

kama110.字符串接龙

	/*** 遍历每个字母和每个位置替换* @param args*/public static void main(String[] args) {//读取Scanner scan = new Scanner(System.in);int n = scan.nextInt();scan.nextLine();String startStr=scan.next();String endStr=scan.next();scan.nextLine();//set集合来存储字符串Set<String> set = new HashSet<>();for(int i=0;i<n;i++) {String s = scan.nextLine();set.add(s);}int res = countPath(set,startStr,endStr);System.out.println(res);scan.close();}public static int countPath(Set<String> set,String startStr,String endStr) {//path集合来标记走过的路径，BFS是向外扩散，无向图需要记录不走回头路Map<String,Integer> map = new HashMap<>();map.put(startStr, 1);//创造队列Queue<String> queue = new LinkedList<>();queue.offer(startStr);int path=0;while(!queue.isEmpty()) {String str = queue.poll();path = map.get(str);for(int i=0;i<str.length();i++) {char[] str1 = str.toCharArray();//遍历26个字母求得新字符串for(char j='a';j<='z';j++) {str1[i]=j;String newStr = new String(str1);//当走到end字段则返回if(newStr.equals(endStr)) return path+1;//将路径加入map中if(set.contains(newStr)&&!map.containsKey(newStr)) {map.put(newStr,path+1);queue.offer(newStr);}}}}return 0;}

kama105.有向图的完全可达性

	public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[][] isoland = new int[n+1][n+1];for(int i=0;i<m;i++) {int x = scan.nextInt();int y = scan.nextInt();isoland[x][y]=1;}Queue<Integer> queue = new LinkedList<>();queue.add(1);Set<Integer> set = new HashSet<>();set.add(1);while(!queue.isEmpty()) {int now = queue.remove();for(int i=1;i<=n;i++) {if(isoland[now][i]==1&&!set.contains(i)) {set.add(i);queue.add(i);}}}if(set.size()==n) {System.out.println(1);}else {System.out.println(-1);}scan.close();}

kama106.岛屿的周长

	public static int[][] step = {{1,0},{0,1},{-1,0},{0,-1}};public static void main(String[] args) {//读取Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[][] isoland = new int[n][m];for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {isoland[i][j]=scan.nextInt();}}int sum=0;for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {//如果该位置是岛屿，计算边长if(isoland[i][j]==1) {int count=0;//上下左右for(int k=0;k<4;k++) {int k1=i+step[k][0];int k2=j+step[k][1];if(k1<0||k1>n-1||k2<0||k2>m-1) {count++;}else {if(isoland[k1][k2]==0)count++;}}sum+=count;}}}System.out.println(sum);scan.close();}