Problem 40 Paths in the Grid - No Output?
Back to Problem Solutions forum
I was wondering if anyone used the C/C++ code running tools provided to generate output correctly? I can compile and execute my code fine in VS 2010 but when I try to use the code running tools provided, the output generated is blank. I had to copy and paste output from VS. Just curious if it is something weird in my code or if the code running tools for C/C++ had some issue with the input.
Hi! thanks for your message, I'll try to check it with your code and get back with the answer.
Verily there could be somethiing wrong :(
It's me, Admin again - I've played a bit with your solution and found that after certain
point of execution your rows variable becomes zero. I investigated bit further and
I'm afraid there is a small problem with your code, in this line:
if(1!=scanf("%s", &c)) printf("Error scanf 2 ");
See, the %s is not correct specification for reading char variable. Instead it reads
sequence of characters as zero-terminated string. So it starts with the address of c
variable and then goes on spoiling the other variables memory, eventually nullifying rows.
Such behavior greatly depends on compiler and compiler options (i.e. on how variables are
ordered and packed in memory by compiler) - so probably when you run it locally, your settings
did not lead to overwriting crucial memory locations (possibly due to byte alignment so that
char variable used 4 bytes instead of one).
I think that you can fix it easily using %c type specification instead, i.e.:
if(1!=scanf("%c", &c)) printf("Error scanf 2 ");
Hope my suspicions make sense and could be helpful. Please feel free to write for more help if necessary!
Hi Admin, you were correct.
I used %s because I couldn't get %c to work initially due to the whitespace characters between each space.
I used %s to avoid this but didn't think about the implications this might have.
I got it working correctly with your advice plus some modification.
if(1!=scanf("%*[ \n\t]%c", &c)) printf("Error scanf 2 ");
This allows scanf to properly ignore the leading whitespace characters for all characters read and fixed my problem. Thank you again for your help!
Hello, I have created a code that works very well with the example, I modify the example and everything is fine. However with larger matrices it does not output.
The algorithm is more or less as follows, we take the number of rows and columns and create all possible arrays with 1 and 0 so that 0 is a downward motion and 1 is a rightward motion, thus the size of the arrangement is the total of movements: rows + columns -2, and the number of 1 and 0 remains constant. then we test each way and if in the hay an "X" we do not count, if no "X" appears we add one. It seems that it is not yet optimal enough, I am really frustrated. Thank you
This problem undeed can be solved more efficiently. If you think dynamic programming is about using arrays, you are not quite right. It is about storing solutions for smaller subproblems and reducing problem to smaller ones.
Try think how you can count paths for N x M grid if you already have counted paths for (N - 1) x M and N x (M - 1) grids and stored these results. And if you find the way to calculate it, you easily come to solution.