10422 - Knights in FEN

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

several test cases

Post by Sedefcho » Sat Jun 18, 2005 4:41 pm

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

Post by rushel » Thu Jul 28, 2005 12:26 pm

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
Location: Bangladesh
Contact:

10422

Post by DP » Tue Aug 15, 2006 10:39 am

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.

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

Re: 10422

Post by Martin Macko » Tue Aug 15, 2006 11:48 am

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
Location: Bangladesh
Contact:

Post by DP » Tue Aug 15, 2006 1:25 pm

Can someone tell me, how the following Input produce 8 move(s) for knight?

Code: Select all

11111
00111 
00111
0 001
00000 
I found it from board. PLease help me!!!

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

Post by slxst » Tue Oct 30, 2007 7:50 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 
I found it from board. PLease help me!!!
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

Post by stcheung » Sat Jan 10, 2009 10:14 am

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
Location: Bangladesh
Contact:

Re: 10422 - Knights in FEN

Post by Imti » Fri Feb 11, 2011 1:53 pm

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.

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10422 - Knights in FEN

Post by mahade hasan » Sat Sep 01, 2012 4:41 pm

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

Post by brianfry713 » Wed Sep 05, 2012 1:32 am

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

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10422 - Knights in FEN

Post by mahade hasan » Sat Sep 08, 2012 7:08 pm

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

Post by brianfry713 » Mon Sep 10, 2012 10:08 pm

mahade hasan 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.
Check input and AC output for thousands of problems on uDebug!

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10422 - Knights in FEN

Post by mahade hasan » Wed Sep 12, 2012 7:56 pm

brianfry713 wrote:
mahade hasan 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

Post by brianfry713 » Wed Sep 12, 2012 8:09 pm

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!

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10422 - Knights in FEN

Post by mahade hasan » Wed Sep 12, 2012 8:32 pm

brianfry713 wrote: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.
The code found at https://ideone.com/4Q7TX
is also wrong answer code..........
we r surrounded by happiness
need eyes to feel it!

Post Reply

Return to “Volume 104 (10400-10499)”