陈正磊


私信TA

用户名:RossTran

访问量:13475

签 名:

晨兴理荒秽,带月荷锄归。

等  级
排  名 177
经  验 6660
参赛次数 15
文章发表 34
年  龄 0
在职情况 学生
学  校 湖北生物科技职业学院
专  业

  自我简介:

解题思路:
题目有问题,原题应该是这样。细胞是1到9,而不是11到99.

一矩形阵(n*m)列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。(细胞数字指1到9)
0234500067
1034560500
2045600671
0000000089

那么这题就是找到一个细胞,就向上下左右寻找细胞,寻找的地方就标记一下,下次不再寻找,寻找的次数就是细胞的个数。
注意事项:

参考代码:

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	public static int next[][]={{0,1},{1,0},{0,-1},{-1,0}};//下一步
	public static int flag[][];//标记是否走过
	
	public static class Q{
		int x;
		int y;
		public  Q(){};
		public  Q(int _x,int _y){x=_x;y=_y;}
	}
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int n=sc.nextInt();
    	int m=sc.nextInt();
    	char arr[][]=new char[n][m];
    	flag=new int[n][m];
    	//输入
    	for (int i = 0; i < arr.length; i++) {
			arr[i]=sc.next().toCharArray();
		}
    	//bfs,
    	int count=0;//细胞个数
    	for (int i = 0; i <n; i++) {
			for (int j = 0; j <m; j++) {
				if (arr[i][j]!='0' && flag[i][j]==0) {//开始搜索
					flag[i][j]=1;
					LinkedList<Q> que=new LinkedList<Main.Q>();
					que.add(new Q(i,j));//添加首列
					bfs(arr, i, j, que);count++;//搜索一次加一次
				}
			}
		}
    	System.out.println(count);
    }
    
    public static void bfs(char arr[][],int x,int y,LinkedList<Q> que) {
          while (que.size()!=0) {
        	  Q first=que.poll();//取出头列,并删除
        	  for (int i = 0; i <4; i++) {
      			int dx=first.x+next[i][0];
      			int dy=first.y+next[i][1];
      			if (dx>=0 && dx<arr.length && dy>=0 && dy<arr[0].length
      					&& flag[dx][dy]==0 && arr[dx][dy]!='0') {
      				flag[dx][dy]=1;//标记走过
      				que.add(new Q(dx,dy));
      			}
      		}
		}
          
	}
   
    

}


 

0.0分

2 人评分

  评论区

墙都不扶就服你
2020-10-14 11:16:46
  • «
  • 1
  • »