# E1 - the white knight, AC :)

WA, on problem: [http://www.codechef.com/problems/E1][1]
my code: [http://ideone.com/OWMH40][2]

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
int t, n, a[1010][1010], x, y;
char s[1000];
scanf("%d", &t);
while(t--) {
memset(a, 0, sizeof(a));
scanf("%d", &n);
for(int i=0; i<n; i++) {
scanf("%s", s);
for(int j=0; j<n; j++) {
if(s[j]=='P') a[i+5][j+5]++;
else if(s[j]=='K') x=i+5, y=j+5;
}
}
for(int j=n+4; j>=y; j--) {
for(int i=n+4; i>4; i--) {
a[i][j]+=max(max(a[i+1][j+2], a[i+2][j+1]), max(a[i-1][j+2], a[i-2][j+1]));
}
}
printf("%d\n", a[x][y]);
}
return 0;
}
``````

thanks beforehand.

idea is, i used extra array indices instead of checking boundaries, also i calculated the max value among 4 available moves, when doing this i recursively(or iteratively, i dont know) loop from (supposed to be)leftmost array boundary, when reaching column of K(pos y here) stop loop.
[1]: http://www.codechef.com/problems/E1
[2]: http://ideone.com/OWMH40

codechef E1 - “the white knight” : http://www.codechef.com/problems/E1

codechef E1 - “the white knight” tutorial 1 : http://www.codechef.com/wiki/tutorial-white-knight

codechef E1 - “the white knight” tutorial 2 may be : http://discuss.codechef.com/questions/1363/code-e1-the-white-knight

codechef E1 - “the white knight” solution : http://ideone.com/tw6NWO

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
int t, n, a[1010][1010], x, y;
char s[1010];
scanf("%d", &t);
while(t--) {
memset(a, 0, sizeof(a));
scanf("%d", &n);
for(int i=0; i<n; i++) {
scanf("%s\n", s);
for(int j=0; j<n; j++) {
if(s[j]=='P') a[i+5][j+5]++;
else if(s[j]=='K') x=i+5, y=j+5;
}
}
for(int j=n+4; j>4; j--) {
for(int i=n+4; i>4; i--) {
a[i][j]+=max(max(a[i+1][j+2], a[i+2][j+1]), max(a[i-1][j+2], a[i-2][j+1]));
}
}
printf("%d\n", a[x][y]);
}
return 0;
}
``````

note: i tried many times and got TLE or WA. eventually got AC. i just used extra space in order not to check edge cases. i also increased char and int array size, and also dont forget to read newline at the end of string(`scanf("%s\n", string)`).

1 Like
//