999. 车的可用捕获量

#999. 车的可用捕获量

题目描述
2020/3/26每日一题


解题思路
这道题最难的就是读懂题目了，一次移动指上下左右四个方向各移动一次，如果碰到黑色小兵就可以吃掉，如果碰到边界或者白色象就不能吃。巧妙的处理方式就是定义四个方向的坐标，就像是图像处理里处理邻域的思想。

public int numRookCaptures(char[][] board) {
        //定义上下左右四个方向
  	int[] dx = {-1,1,0,0};
  	int[] dy = {0,0,-1,1};
  	int kill = 0;
  	for (int i = 0; i < 8; i++) {
   	for (int j = 0; j < 8; j++) {
    		if (board[i][j] == 'R') {  //先找到象位置，然后向上下左右四个方向搜寻
     			for (int p = 0; p < 4; p++) {
      				int x = i,y = j;
      				while (true) {
       					x += dx[p];
       					y += dy[p];
       					if(x <=0 || x >= 8 || y <= 0 || y >= 8 || board[x][y] == 'B') 
        				//如果碰到边界或者黑象，进行下个方向的搜寻
        				break; 
       					if (board[x][y] == 'p') {
        					kill++;
        					break;
       					}
       				}
     			}
    		}
   	} 
  	}
  	return kill;
}      

时间复杂度双重循环O(n2)，空间复杂度O(1)
运行结果：