The White KnightProblem code: E1 |
All submissions for this problem are available.
You are given a chessboard of size NxN. There is a white knight and several black pawns located on the board. The knight can move similarly to the normal knight in the game of chess; however it can only move towards the right of the board (see the below figure).
The mission of the knight is to capture as many black pawns as possible. Its journey ends when it moves to the rightmost column of the board.
Compute the maximum number of black pawns the white knight can capture.
Input
The first line contains t, the number of test cases (about 10). Then t test cases follow.
Each test case has the following form:
- The first line contains N, the size of the chessboard (4 ? N ? 1000).
- Then N lines follow, each line containing N characters which may be '0', 'K' or 'P', corresponding to the empty cell, the white knight, and the black pawn, respectively. There is exactly one 'K' character in the whole of the board.
Output
For each test case, print in a single line the maximum number of black pawns that can be captured.
Example
Input: 1 5 K.... ..P.. .P... ...P. ..... Output: 2
| Author: | admin |
| Date Added: | 5-06-2009 |
| Time Limit: | 4 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.
My code was accepted ,but it
My code was accepted ,but it says it ran for 2.85s and used 7516 KB of memory.
The time limit above says 2s,am i missing something here....
There are multiple input
There are multiple input files and the total time displayed is the sum of the times taken for the different input files.
in the problem statement its
in the problem statement its given that blank cells will be denoted by zero..
in sample input '.' is given..
explanation needed please...
thanx neways.. it doesnt
thanx neways.. it doesnt matter as we hace to check for K and P only..
should have read the whole question first..
i am getting correct answer
i am getting correct for the
i am getting correct answer
thanx... neways. got accepted
i am getting correct answer
i am getting correct answer for the sample input but still i am getting wrong answer when i submit my code. as far as i think my logic is correct. can you provide another test case
@admin i view the solution
@admin
i view the solution from this problem submmited at the 1st positon and i copied the source code from solution and run it on my machine and i entered the same sample input and the output of the submitted solution is 0 and not match with require output then how it succsess fully submitted...
pls help.....
the N lines of a test
the N lines of a test case...do they represent the status of a row, or column??
They are rows.
They are rows.
@admin: There should be more
@admin:
There should be more test cases.
I am not able to find why my solution gives a wrong answer when submitted. Please give any test case where it fails.
Or it'll be nice of you if you can tell me where I am doing mistake.
My solution: http://www.codechef.com/viewsolution/425076
No, there shouldn't be more
No, there shouldn't be more test cases. The sample input is only there to make sure you understood the problem; it is always your job to generate real test cases as part of solving the problem.
I haven't looked at your main algorithm, but I don't think you understand how the memset function works.
@Stephen: Removed memset !
@Stephen:
Removed memset ! Still wrong!
http://www.codechef.com/viewsolution/425128
Algorithm works as:
1. board array contains the entire position of pawns and the initial position of knight as given in input.
2. knight array will keep all the possible positions of knight.
3. eaten array will keep the value of eaten pawns for possible positions of knight.
4. every row of board is scanned and the positions of knight is observed, for every position the next 4 positions are determined and corresponding values of eaten array are updated.
5. If a pawn is there on the next knight position the eaten value is updated by current position's eaten value plus one, this is done if new value is greater than previous value.
6. If there is no pawn on the next knight position the the eaten value is simply copied, this is done if the previous value is smaller than the new value.
This way the last row of eaten array contains all the possible eaten pawn values starting from the knight's initial position. From that row the largest value is picked up giving us the result!!
Are you sure your board is
Are you sure your board is oriented the right way?
Problem says the knight goes
Problem says the knight goes from left to right. I assume it to go from top to bottom. Either way you do, you achieve the same thing. Right?
So will you consider
So will you consider capturing a pawn which starts above the knight like you are allowed to?
I am not grabbing any pawn
I am not grabbing any pawn above the position of the knight!!
If you see first the knight array is empty. Inside the solve function first the position of the knight is determined and after that using that position the algorithm proceeds and captures the pawns which are below that position.
That's my point. The problem
That's my point. The problem statement clearly shows the knight is allowed to move upwards.
That was blunder!! Thank
That was blunder!! Thank you.
Fixed that but still runtime error! :( :(
http://www.codechef.com/viewsolution/425852
Runtime errors are easy to
Runtime errors are easy to debug. In your sort of code it is almost always due to issues with array indices. Check them carefully and you'll find your mistake (albeit indirectly).
Now 'm loosing my temper!! I
Now 'm loosing my temper!!
I got why it was runtime error but now struck by wrong answer!
http://www.codechef.com/viewsolution/426336
Please help. I have no more patience.
Arrrrgggggghhh..... It's
Arrrrgggggghhh.....
It's running good on almost all test cases I have!!!!!! :( :( :( :(
Stephen! F1 !!!!!
Stephen! F1 !!!!!
@Admin: May I know for which
@Admin:
May I know for which test case my solution is giving wrong output?? I'm damn tired checking my solution! Please give me the test case for which my input is failing!!
@Admin: Tutorial to this
@Admin:
Tutorial to this problem (http://www.codechef.com/wiki/tutorial-white-knight) says to move back from the right most column. Whats wrong if we move from left to right??
@Admin My code is not
@Admin
My code is not accepted giving a runtime error stating the reason : SIGSEGV.
When I try to submit , it goes into processing forever but meanwhile I get an e-mail stating the above.
My code runs just fine when I try it on my computer.
http://www.codechef.com/views
http://www.codechef.com/viewsolution/499067
plz tel me y m getting wrong err.
when i have submitted in c
@Admin: plz tell me for
@admin.. could you plz tell
I want to know can this
@admin ...i got TLE ...pls