10422

Sedefcho · 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

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 · 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 · 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.

Martin Macko · 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 · 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

I found it from board. PLease help me!!!

slxst · 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 · 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 · 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

My code tried to reach final codition from given condition.

mahade hasan · 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]

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

Try the I/O posted in this thread.

mahade hasan · 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..........

brianfry713 · 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.

mahade hasan · 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......

brianfry713 · 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.

mahade hasan · 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..........

OJ Board

10422 - Knights in FEN

several test cases

10422

Re: 10422

Re: 10422 - Knights in FEN

Re: 10422 - Knights in FEN

Re: 10422 - Knights in FEN

Re: 10422 - Knights in FEN

Re: 10422 - Knights in FEN

Re: 10422 - Knights in FEN

Re: 10422 - Knights in FEN

Re: 10422 - Knights in FEN

Re: 10422 - Knights in FEN