剑指Offer（六十六）机器人的运动范围（Java版）

　　描述
　　地上有一个rows行和cols列的方格。坐标从〔0，0〕到〔rows1，cols1〕。一个机器人从坐标〔0，0〕的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于threshold的格子。例如，当threshold为18时，机器人能够进入方格〔35，37〕，因为353718。但是，它不能进入方格〔35，38〕，因为353819。请问该机器人能够达到多少个格子？
　　数据范围：0lethresholdle15threshold15，1lerows，colsle1001rows，cols100进阶：空间复杂度O（nm）O（nm），时间复杂度O（nm）O（nm）示例1
　　输入：1，2，3
　　返回值：3示例2
　　输入：0，1，3
　　返回值：1示例3
　　输入：10，1，100
　　返回值：29
　　说明：
　　〔0，0〕，〔0，1〕，〔0，2〕，〔0，3〕，〔0，4〕，〔0，5〕，〔0，6〕，〔0，7〕，〔0，8〕，〔0，9〕，〔0，10〕，〔0，11〕，〔0，12〕，〔0，13〕，〔0，14〕，〔0，15〕，〔0，16〕，〔0，17〕，〔0，18〕，〔0，19〕，〔0，20〕，〔0，21〕，〔0，22〕，〔0，23〕，〔0，24〕，〔0，25〕，〔0，26〕，〔0，27〕，〔0，28〕这29种，后面的〔0，29〕，〔0，30〕以及〔0，31〕等等是无法到达的示例4
　　输入：5，10，10
　　返回值：21第一种解法
　　使用dfs（深度优先搜索）来解决，需要注意的一点。得防止重复的点二次计数。代码如下int〔〕〔〕arrnull；intcount0；publicintfirstMovingCount（intthreshold，introws，intcols）｛if（rows1cols1）｛returncount；｝if（threshold0）｛returncount；｝arrnewint〔rows〕〔cols〕；dsf（threshold，rows，cols，0，0）；returncount；｝publicvoiddsf（intthreshold，introws，intcols，introw，intcol）｛if（row0rowrowscol0colcolsarr〔row〕〔col〕1）｛return；｝if（check（row）check（col）threshold）｛return；｝arr〔row〕〔col〕1；count；dsf（threshold，rows，cols，row1，col）；dsf（threshold，rows，cols，row1，col）；dsf（threshold，rows，cols，row，col1）；dsf（threshold，rows，cols，row，col1）；｝intcheck（intnum）｛intsum0；while（num0）｛sum（num10）；numnum10；｝returnsum；｝第二种解法
　　使用bfs（广度优先搜索）来解决。对于bfs的特性，采用队列来实现是最好的，因为队列是先进先出，离他最近的访问完之后加入到队列中，最先入队的也是最先出队的，代码如下int〔〕〔〕arrnull；intcount0；intcheck（intnum）｛intsum0；while（num0）｛sum（num10）；numnum10；｝returnsum；｝publicintsecondMovingCount（intthreshold，introws，intcols）｛if（rows1cols1）｛returncount；｝if（threshold0）｛returncount；｝arrnewint〔rows〕〔cols〕；Queueint〔〕queuenewLinkedList（）；queue。add（newint〔〕｛0，0｝）；while（！queue。isEmpty（））｛int〔〕pollqueue。poll（）；intipoll〔0〕；intjpoll〔1〕；if（irowsjcolsarr〔i〕〔j〕1（check（i）check（j）threshold））｛continue；｝arr〔i〕〔j〕1；count；queue。add（newint〔〕｛i1，j｝）；queue。add（newint〔〕｛i，j1｝）；｝returncount；｝