c++ - GridWalk CodeEval 实现问题

Question

这是我在 CodeEval 上遇到的问题。这是我花了 4 个小时解决的问题。两年前我在这里看到了另一篇 CodeEval GridWalk Problem 帖子，但它对我没有任何帮助。如果有人有过这个问题的经验，请阅读我的代码，因为我不知道我做错了什么。

有一只猴子可以在平面网格上走动。猴子一次可以向左、向右、向上或向下移动一格。也就是说，猴子可以从 (x, y) 到达 (x+1, y)、(x-1, y)、(x, y+1) 和 (x, y-1)。 x坐标的绝对值的位数之和加上y坐标的绝对值的位数之和小于或等于19的点是猴子可以访问的。例如，点 (59, 79) 是不可访问的，因为 5 + 9 + 7 + 9 = 30，大于 19。又如:点 (-5, -7) 是可访问的，因为 abs(-5) + abs(-7) = 5 + 7 = 12，小于 19。如果猴子从 (0, 0) 开始，包括 (0, 0) 本身，它可以访问多少个点？输入样本:

该程序没有输入。输出样本:

打印猴子可以访问的点数。它应该打印为整数 - 例如，如果点数是 10，则打印“10”，而不是“10.0”或“10.00”等。

在文件中提交您的解决方案(某些文件名)。(py2| c| cpp| java| rb| pl| php| tcl| clj| js| scala| cs| m| py3| hs| go| bash| lua)或使用在线编辑器。

#include <stdio.h>
#include <math.h>

int z = 0, counter = 0, x = 0, y = 0, d = -1;

int verified(int x, int y);

int fill();

int main(void){
printf("%d",fill());
return 0;
}

//(x+1, y), (x-1, y), (x, y+1), and (x, y-1)

int fill(){
int i = 0;
while(d<1000000){  //I don't know how to make it so the program doesn't need a 
d++; i++;          //dimension for scanning. I have to end the loop somehow.

if(verified(x,y)){ //scan each point
                   //if x and y are accessible or "verified", increase point counter
counter++;
}else{;}  // do nothing

if((y%2)!= 0){  //increment each point
y += i;
continue;
}else if ((x%2)!=0){
x += i; 
continue;
}else if ((y%2) == 0){
y -= i;
continue;
}else if((x%2) == 0){
x -= i;
continue;
}



}
return counter; //return how many accessible points there are
}

int verified(int x , int y){
int r, digit = 0;
x = abs(x); y = abs(y);                //make x and y absolute
z = x * pow(10, (int)log10(y)+1) + y;
   //^append both values together(eg. x and y become xy)

while (z > 0) {   
 r = z % 10;        
 digit += abs(r);   // add all the digits of the sum together
 z /= 10;
}

if(digit <=19)   //if the sum is less than  or equal to 19, it's true
return 1;
else
return 0;
}

我的这个程序的输出是 575199。这显然不是写入答案。

Answer 1

首先，你不需要做这样的事情z = x * pow(10, (int)log10(y)+1) + y; 因为 log10 函数的强制转换 (int) 总是向下舍入，所以会有两种情况，当 y 是 10 的 pow 时，以及当 y 不是 10 的 pow 时，这显然不适合这部分。您可以通过逐个计算数字之和来解决此问题，先计算 x，然后计算 y，不需要将它们组合起来。

第二，如果我没记错的话，你只能从一个可访问点移动到另一个可访问点，所以这部分再次是错误的:

if((y%2)!= 0){  //increment each point
    y += i;
    continue;
}else if ((x%2)!=0){
    x += i; 
    continue;
}else if ((y%2) == 0){
    y -= i;
    continue;
}else if((x%2) == 0){
    x -= i;
    continue;
}

盲目增加x和y并不能保证点(x,y)可达，这部分应该使用BFS或DFS处理