機器人的運動範圍

機器人的運動範圍

地上有一個m*n的方格，機器人從坐標（0,0）出發，每次可以上下左右移動一個格子。

要求格子的坐標各個位數之和不能超過給定的閾值。問機器人能走多少個格子。

思路：機器人從坐標（0,0）出發，當進入坐標為（i，j）的格子時，判斷機器人是否能夠進入。

參考代碼：

root@gt:/home/git/Code# ./a.out 1484root@gt:/home/git/Code# cat robot.c #include <stdio.h>#include <stdlib.h>#include <string.h>int getSum(int number){ int sum = 0; while(number > 0) { sum += number % 10; number /= 10; } return sum;}int sum(int thread,int row,int col){ int ans = 0; if(getSum(row) + getSum(col) <= thread) ans = 1; return ans;}int check(int thread,int rows,int cols,int row,int col,char* visited){ int checkAns = 0; if(row >=0 && col >=0 && row < rows && col < cols && !visited[row * cols + col] && sum(thread,row,col)) checkAns = 1; return checkAns;}int core(int thread,int rows,int cols,int row,int col,char* visited){ int count = 0; if(check(thread,rows,cols,row,col,visited)) { visited[row * cols + col] = 1; count = 1 + core(thread,rows,cols,row - 1,col,visited) + core(thread,rows,cols,row + 1,col,visited) + core(thread,rows,cols,row,col - 1,visited) + core(thread,rows,cols,row,col + 1,visited); } return count;}int movingCount(int thread,int rows,int cols){ if(thread < 0 || rows < 1 || cols < 1) return 0; char* visited = (char*)malloc((rows * cols)*sizeof(char)); memset(visited,0,(rows * cols)*sizeof(char)); int count = core(thread,rows,cols,0,0,visited); free(visited); return count;}int main(){ int rows = 40; int cols = 40; int ans = 0; int thread = 18; ans = movingCount(thread,rows,cols); printf("%d
",ans); return 0;}

推薦閱讀：