@jtahstu 2017-09-15T02:07:41.000000Z 字数 1354 阅读 2313

# 水池数目（深搜）

算法

2
3 4
1 0 0 0
0 0 1 1
1 1 1 0
5 5
1 1 1 1 0
0 0 1 0 1
0 0 0 0 0
1 1 1 0 0
0 0 1 1 1

2
3

## 代码

# author: jtusta# contact: root@jtahstu.com# site: http://www.jtahstu.com# software: RubyMine# time: 2017/6/9 22:08class PollsNum  def initialize    @a = []    @n = 0    @m = 0    @count = 0  end  def input    t = gets.strip    for x in 1..t.to_i      # 初始化一下      @a = []      @count = 0      # 输入一个二维数组      l = gets.strip.split(/\s+/)      @n = l[0].to_i      @m = l[1].to_i      for i in 1..@n        line = gets.split(/\s+/)        @a[i] = []        for j in 1..@m          @a[i][j] = line[j-1].to_i        end      end      # solve      self.solve    end  end  # 深搜  def dfs(i,j)    if i-1>0 && @a[i-1][j]==1      @a[i-1][j]=0      self.dfs(i-1,j)    end    if i<@n && @a[i+1][j]==1 # 右      @a[i+1][j]=0      self.dfs(i+1,j)    end    if j-1>0 && @a[i][j-1]==1 # 上      @a[i][j-1]=0      self.dfs(i,j-1)    end    if j<@m && @a[i][j+1]==1 # 下      @a[i][j+1]=0      self.dfs(i,j+1)    end  end  def solve    for i in 1..@n      for j in 1..@m        if @a[i][j]==1          @count += 1          @a[i][j]=0          self.dfs(i,j)        end      end    end    p @count  endendpolls = PollsNum.newpolls.input

/usr/bin/ruby -e $stdout.sync=true;$stderr.sync=true;load(\$0=ARGV.shift) /Users/jtusta/Documents/Code/Ruby/algorithm/polls_num.rb23 41 0 0 0 0 0 1 11 1 1 025 51 1 1 1 00 0 1 0 10 0 0 0 01 1 1 0 00 0 1 1 13Process finished with exit code 0

• 私有
• 公开
• 删除