## 10422 - Knights in FEN

Moderator: Board moderators

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### several test cases

Here are several test cases from an ACC
program ( for anyone who might be interested ).

INPUT

Code: Select all

``````9
01011
110 1
01110
01010
00100
10110
01 11
10111
01001
00000
11111
01111
00 11
00001
00000
11111
01111
00110
00001
000 0
11111
0111
00111
00001
00000
11111
00111
00111
0 001
00000
11011
110 1
00110
01010
00100
11111
01111
0011
00001
00000
11111
01111
0001
10001
00000``````

OUTPUT

Code: Select all

``````Unsolvable in less than 11 move(s).
Solvable in 7 move(s).
Solvable in 0 move(s).
Solvable in 3 move(s).
Solvable in 1 move(s).
Solvable in 8 move(s).
Unsolvable in less than 11 move(s).
Solvable in 2 move(s).
Solvable in 4 move(s).``````

Good luck !

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

### 10422

I was trying to reach given configuration to final using backtracking and
pruning but get WA few times.
Then i try to reach final to given and get AC:)
I realize that after testing with the following input:
5 * 5 matrix with spaces ( right no knights ) and
its not necessery there always be 24 knights.(nothins describ like tha in
prob statement)
I hope this help

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:

### 10422

Can someone tell me why WA???

Code: Select all

``````#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char board[6][6];
int sr[5][5];
int goal[5][5]={
1,1,1,1,1,
0,1,1,1,1,
0,0,-1,1,1,
0,0,0,0,1,
0,0,0,0,0,
};
int min,sx,sy;
bool visit[5][5];
int check()
{
int i,j;
for(i=0;i<5;i++){
for(j=0;j<5;j++){
if(sr[i][j]!=goal[i][j]) return false;
}
}
return true;
}
void dfs(int srx,int sry,int cn)
{
if(srx<0||sry<0) return;
if(srx>4||sry>4) return;
if(cn>10) return;
if(check()){if(min>cn) min=cn;return;}
if(visit[srx+1][sry+2]==false){
int temp=sr[srx][sry]=sr[srx+1][sry+2];
sr[srx+1][sry+2]=-1;
visit[srx+1][sry+2]=true;
dfs(srx+1,sry+2,cn+1);
sr[srx+1][sry+2]=temp;
sr[srx][sry]=-1;
visit[srx+1][sry+2]=false;
}
if(visit[srx-1][sry+2]==false){
int temp=sr[srx][sry]=sr[srx-1][sry+2];
sr[srx-1][sry+2]=-1;
visit[srx-1][sry+2]=true;
dfs(srx-1,sry+2,cn+1);
sr[srx-1][sry+2]=temp;
visit[srx-1][sry+2]=false;
sr[srx][sry]=-1;
}
if(visit[srx+1][sry-2]==false){
int temp=sr[srx][sry]=sr[srx+1][sry-2];
sr[srx+1][sry-2]=-1;
visit[srx+1][sry-2]=true;
dfs(srx+1,sry-2,cn+1);
sr[srx+1][sry-2]=temp;
sr[srx][sry]=-1;
visit[srx+1][sry-2]=false;
}
if(visit[srx-1][sry-2]==false){
int temp=sr[srx][sry]=sr[srx-1][sry-2];
sr[srx-1][sry-2]=-1;
visit[srx-1][sry-2]=true;
dfs(srx-1,sry-2,cn+1);
sr[srx-1][sry-2]=temp;
sr[srx][sry]=-1;
visit[srx-1][sry-2]=false;
}
//
if(visit[srx+2][sry+1]==false){
int temp=sr[srx][sry]=sr[srx+2][sry+1];
sr[srx+2][sry+1]=-1;
visit[srx+2][sry+1]=true;
dfs(srx+2,sry+1,cn+1);
sr[srx+2][sry+1]=temp;
sr[srx][sry]=-1;
visit[srx+2][sry+1]=false;
}
if(visit[srx-2][sry+1]==false){
int temp=sr[srx][sry]=sr[srx-2][sry+1];
sr[srx-2][sry+1]=-1;
visit[srx-2][sry+1]=true;
dfs(srx-2,sry+1,cn+1);
sr[srx-2][sry+1]=temp;
sr[srx][sry]=-1;
visit[srx-2][sry+1]=false;
}
if(visit[srx+2][sry-1]==false){
int temp=sr[srx][sry]=sr[srx+2][sry-1];
sr[srx+2][sry-1]=-1;
visit[srx+2][sry-1]=true;
dfs(srx+2,sry-1,cn+1);
sr[srx+2][sry-1]=temp;
sr[srx][sry]=-1;
visit[srx+2][sry-1]=false;
}
if(visit[srx-2][sry-1]==false){
int temp=sr[srx][sry]=sr[srx-2][sry-1];
sr[srx-2][sry-1]=-1;
visit[srx-2][sry-1]=true;
dfs(srx-2,sry-1,cn+1);
sr[srx-2][sry-1]=temp;
sr[srx][sry]=-1;
visit[srx-2][sry-1]=false;
}
return;
}
int main()
{
int tst,i,j;
char ss[100];
gets(ss);
sscanf(ss,"%d",&tst);
while(tst--){
for(i=0;i<5;){
gets(board[i]);
if(board[i][0]=='\0') continue;
else i++;
}
for(i=0;i<5;i++){
for(j=0;j<5;j++){
if(board[i][j]=='1') sr[i][j]=1;
else if(board[i][j]=='0') sr[i][j]=0;
else if(board[i][j]==' '){sr[i][j]=-1;sx=i;sy=j;}
}
}
memset(visit,false,sizeof(visit));
min=1<<30;
dfs(sx,sy,0);
if(min>10) printf("Unsolvable in less than 11 move(s).\n");
else printf("Solvable in %d move(s).\n",min);
}
return 0;
}
``````
help would be appreciated.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: 10422

There is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewto ... ight=10422 and http://online-judge.uva.es/board/viewto ... ight=10422)
forum 'Volume CIV' description wrote:All about problems in Volume CIV. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
Can someone tell me, how the following Input produce 8 move(s) for knight?

Code: Select all

``````11111
00111
00111
0 001
00000
``````

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am
DP wrote:Can someone tell me, how the following Input produce 8 move(s) for knight?

Code: Select all

``````11111
00111
00111
0 001
00000
``````
This reply took 1 year but in case anyone cares anymore, yes the correct output is "Solvable in 8 move(s)."

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### Re: 10422 - Knights in FEN

If you are struggling to solve this problem with backtracking/dfs/2-way bfs then you might as well try the precalc idea that someone mentioned already. Since the board has 25 squares, and each square has only 3 different possibilities, you can use a 64-bit integer to uniquely represent each different board configuration. By starting from the final configuration, and doing bfs, you can easily figure out all the board configuations reachable within 10 moves, and efficiently look them up when processing the input. I think this should be easier to implement.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 10422 - Knights in FEN

Plz anyone see my code...I couldn't understand why I'm getting WA...

Code: Select all

``````#include<stdio.h>
bool vis[10][10];
long board[10][10],mino,store[10][10];
long x[8]={-1,1,-2,2,-1,1,-2,2};
long y[8]={-2,-2,-1,-1,2,2,1,1};
void check(long a,long b,long cost)
{
if(cost>10)
return;
if(a==3&&b==3)
{
long i,j;
for(i=1;i<=5;i++)
for(j=1;j<=5;j++)
if(board[i][j]!=store[i][j])
return;
if(mino>cost)
mino=cost;
return;
}
long c,d,i;
for(i=0;i<8;i++)
{
c=a+x[i];d=b+y[i];
if(c>0&&d>0&&c<6&&d<6&&!vis[c][d])
{
vis[c][d]=1;
board[a][b]=board[c][d];
board[c][d]=3;
check(c,d,cost+1);
vis[c][d]=0;
board[c][d]=board[a][b];
board[a][b]=3;
}
}
}
int main()
{
char str[60000];
long ei,ej,i,j,kase;
for(i=1;i<=5;i++)
{
for(j=i;j<=5;j++)
store[i][j]=1;
for(j=1;j<=i;j++)
store[i][j]=0;
}
store[3][3]=3;store[1][1]=store[2][2]=1;
scanf("%ld",&kase);
getchar();
while(kase--)
{
mino=1000000000;
for(i=1;i<=5;i++)
{
gets(str);
for(j=1;j<=5;j++)
{
vis[i][j]=0;
if(str[j-1]==' ')
{
board[i][j]=3;
ei=i;ej=j;
}
else
board[i][j]=str[j-1]-'0';
}
}
check(ei,ej,0);
if(mino<11)
printf("Solvable in %ld move(s).\n",mino);
else
printf("Unsolvable in less than 11 move(s).\n");
}
return 0;
}
``````
My code just failing at this input

Code: Select all

``````1
11111
00111
00111
0 001
00000
``````
My code tried to reach final codition from given condition.

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 10422 - Knights in FEN

why WWWWWWAAAAAAA...........

Code: Select all

``````[color=#80FF40]
#include<stdio.h>
#include<map>
#include<queue>
#include<iostream>
using namespace std;
string Input="",Target="111110111100 110000100000",S;
typedef pair<pair<int,int>,pair<string,int> >Pair;

int Cal(int I,int K,string St)
{
map<string,int>Map;
queue<Pair>Q;
Q.push(make_pair(make_pair(I,K),make_pair(St,0)));

while(!Q.empty())
{
Pair P=Q.front();
Q.pop();

if(P.second.first==Target||P.second.second>10) return P.second.second;

if(P.first.first-2>-1&&P.first.second-1>-1)
{
S=P.second.first;
S[(P.first.first)*5+P.first.second]=S[(P.first.first-2)*5+P.first.second-1];
S[(P.first.first-2)*5+P.first.second-1]=' ';
if(Map[S]==0)
{
Map[S]=1;
Q.push(make_pair(make_pair(P.first.first-2,P.first.second-1),make_pair(S,P.second.second+1)));
}
}

if(P.first.first-2>-1&&P.first.second+1<5)
{
S=P.second.first;
S[(P.first.first)*5+P.first.second]=S[(P.first.first-2)*5+P.first.second+1];
S[(P.first.first-2)*5+P.first.second+1]=' ';
if(Map[S]==0)
{
Map[S]=1;
Q.push(make_pair(make_pair(P.first.first-2,P.first.second+1),make_pair(S,P.second.second+1)));
}
}

if(P.first.first+2<5&&P.first.second-1>-1)
{
S=P.second.first;
S[(P.first.first)*5+P.first.second]=S[(P.first.first+2)*5+P.first.second-1];
S[(P.first.first+2)*5+P.first.second-1]=' ';
if(Map[S]==0)
{
Map[S]=1;
Q.push(make_pair(make_pair(P.first.first+2,P.first.second-1),make_pair(S,P.second.second+1)));
}
}

if(P.first.first+2<5&&P.first.second+1<5)
{
S=P.second.first;
S[(P.first.first)*5+P.first.second]=S[(P.first.first+2)*5+P.first.second+1];
S[(P.first.first+2)*5+P.first.second+1]=' ';
if(Map[S]==0)
{
Map[S]=1;
Q.push(make_pair(make_pair(P.first.first+2,P.first.second+1),make_pair(S,P.second.second+1)));
}
}

if(P.first.first-1>-1&&P.first.second-2>-1)
{
S=P.second.first;
S[(P.first.first)*5+P.first.second]=S[(P.first.first-1)*5+P.first.second-2];
S[(P.first.first-1)*5+P.first.second-2]=' ';
if(Map[S]==0)
{
Map[S]=1;
Q.push(make_pair(make_pair(P.first.first-1,P.first.second-2),make_pair(S,P.second.second+1)));
}
}

if(P.first.first+1<5&&P.first.second-2>-1)
{
S=P.second.first;
S[(P.first.first)*5+P.first.second]=S[(P.first.first+1)*5+P.first.second-2];
S[(P.first.first+1)*5+P.first.second-2]=' ';
if(Map[S]==0)
{
Map[S]=1;
Q.push(make_pair(make_pair(P.first.first+1,P.first.second-2),make_pair(S,P.second.second+1)));
}
}

if(P.first.first-1>-1&&P.first.second+2<5)
{
S=P.second.first;
S[(P.first.first)*5+P.first.second]=S[(P.first.first-1)*5+P.first.second+2];
S[(P.first.first-1)*5+P.first.second+2]=' ';
if(Map[S]==0)
{
Map[S]=1;
Q.push(make_pair(make_pair(P.first.first-1,P.first.second+2),make_pair(S,P.second.second+1)));
}
}

if(P.first.first+1<5&&P.first.second+2<5)
{
S=P.second.first;
S[(P.first.first)*5+P.first.second]=S[(P.first.first+1)*5+P.first.second+2];
S[(P.first.first+1)*5+P.first.second+2]=' ';
if(Map[S]==0)
{
Map[S]=1;
Q.push(make_pair(make_pair(P.first.first+1,P.first.second+2),make_pair(S,P.second.second+1)));
}
}
}
}

int main()
{
int I,K,L,M,N,Test,Ans;
scanf("%d",&Test);

while(Test--)
{
Input="";
for(I=0;I<5;I++)
{
scanf("\n");
getline(cin, S);
Input+=S;
}

for(I=0;I<5;I++)
for(K=0;K<5;K++)
if(Input[I*5+K]==' ')
{
Ans=Cal(I,K,Input);
break;
}

if(Ans>10) printf("Unsolvable in less than 11 move(s).\n");
else printf("Solvable in %d move(s).\n",Ans);

}

return 0;
}
[/color]``````
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10422 - Knights in FEN

Try the I/O posted in this thread.
Check input and AC output for thousands of problems on uDebug!

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 10422 - Knights in FEN

brianfry713 wrote:Try the I/O posted in this thread.
All are tested n gives right Ans....
but judge give WAAAA WAAA..........
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10422 - Knights in FEN

brianfry713 wrote:Try the I/O posted in this thread.
All are tested n gives right Ans....
but judge give WAAAA WAAA..........
https://ideone.com/4Q7TX
See the I/O above posted by Sedefcho.
Check input and AC output for thousands of problems on uDebug!

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 10422 - Knights in FEN

brianfry713 wrote:
brianfry713 wrote:Try the I/O posted in this thread.
All are tested n gives right Ans....
but judge give WAAAA WAAA..........
https://ideone.com/4Q7TX
See the I/O above posted by Sedefcho.
the respected code produce WA as Well .......
I tried all.....
all gave right ans......
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10422 - Knights in FEN

I copied and pasted the code you posted to https://ideone.com/4Q7TX, ran it on the I/O that Sedefcho posted in this thread, and it didn't match, so that you can see that it's not producing the correct output for those inputs.
Check input and AC output for thousands of problems on uDebug!