601 - The PATH

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

Moderator: Board moderators

sERbU
New poster
Posts: 6
Joined: Thu Apr 08, 2004 10:06 am
Location: Barcelona

601 - The PATH

Post by sERbU »

I always get WA but I don't understand it because I've tested a lot of inputs and there aren't wrongs. Anybody has a valid test ??
I use this input:

Code: Select all

1

W

1

B

1

U

2

WW
BB

2

BU
WU

2

BU
BU

2

UB
UU

2

WW
WW

2

UU
UU

3

WWW
WWW
WWW

3

BBB
BBB
BBB

3

UUU
UUU
UUU

3

WBB
WWU
WBB

3

UUU
WWU
UUU

3

WWU
UUU
WWU

3

BUB
BUB
UUU

3

BBB
BWW
BWW

3

BWU
BWB
WWB

7

WBBUUUU
WWBUWWW
UWBBBWB
BWBBWWB
BWWBWBB
UBWWWBU
UWBBBWW

4

BBBB
WWWB
BWBB
WWBU

6

WBWBUU
BWBBUW
UWBBBW
UBBBUW
UUUUBU
WWBBUW

10

UUUUUUUUUU
UUUUUUUUUU
UUUUUUUUUU
UUUUUUUUUU
UUUUUUUUUU
UUUUUUUUUU
UUUUUUUUUU
UUUUUUUUUU
UUUUUUUUUU
UUUUUUUUUU

0
And this is the output that I've gotten which it seems correct.

Code: Select all

White has a winning path.
Black has a winning path.
There is no winning path.
White has a winning path.
White can win in one move.
Black has a winning path.
Black can win in one move.
White has a winning path.
There is no winning path.
White has a winning path.
Black has a winning path.
There is no winning path.
White can win in one move.
White can win in one move.
White can win in one move.
Black can win in one move.
Black has a winning path.
White can win in one move.
White has a winning path.
Black has a winning path.
There is no winning path.
There is no winning path.
I need more tests for help, please.
Thank you.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Code: Select all

White has a winning path.
Black has a winning path.
White can win in one move.
White has a winning path.
White can win in one move.
Black has a winning path.
Black can win in one move.
White has a winning path.
There is no winning path.
White has a winning path.
Black has a winning path.
There is no winning path.
White can win in one move.
White can win in one move.
White can win in one move.
Black can win in one move.
Black has a winning path.
White can win in one move.
White has a winning path.
Black has a winning path.
Black can win in one move.
There is no winning path.

sERbU
New poster
Posts: 6
Joined: Thu Apr 08, 2004 10:06 am
Location: Barcelona

Post by sERbU »

:cry:

First I'm sorry because my english is very bad although I'm going to try to explain wath's it happen.

I have redone the code as much as 10 times and I always get the correct answer for my input. But I still get Wrong Answer in Online Judge.
My main program makes the work at the next way:
First I look for a winning path for Whites. If I haven't found it then I look for Whites can win in one move.
Second if there isn't any path finished or with one unfilled position for whites, then I look for a winning path for blacks.
After, if there is any path for blacks, I look for Blacks can win in one move.
Finally if trere isn't any path for blacks or whites I write the message there is no winning path.
I always read the input and for every board I store it in vector<vector<pair<bool,char> > >. I store the white matrix at the same way as read it, but not the black matrix which I store in turned position in order to have the home edge in the first column and the target edge in the last column. The boolean in pair means case's status. At first all cases are in false. But I put it in true when I make a path. I've buil two functions. One for the winning paths and other for can win in one move.
Both do calls for any adjacent case wich are the same character or an unfilled position(this case only in function for I can win in one move) until the single case.
In the second function I use an integer num_unfilled, which says me in every call the number of unfilled position for this path.
If I arrive at the single case with one unfilled position I write the message colur can win in one move otherwise the function finish returning false and it doesn't write anything by the output so is the main program which writes there is no winning path if we was at the last case( looking for blacks).
I hope you can understand what I want to say.
Could everybody help me ?? What's wrong in my program ??
This is the last input and the last output that I have gotten.
Thank you.

That's the input:

Code: Select all

1 

W 

1 

B 

1 

U 

2 

WW 
BB 

2 

BU 
WU 

2 

BU 
BU 

2 

UB 
UU 

2 

WW 
WW 

2 

UU 
UU 

3 

WWW 
WWW 
WWW 

3 

BBB 
BBB 
BBB 

3 

UUU 
UUU 
UUU 

3 

WBB 
WWU 
WBB 

3 

UUU 
WWU 
UUU 

3 

WWU 
UUU 
WWU 

3 

BUB 
BUB 
UUU 

3

WWB
UUB
UUU

3 

BBB 
BWW 
BWW 

3 

BWU 
BWB 
WWB 

7 

WBBUUUU 
WWBUWWW 
UWBBBWB 
BWBBWWB 
BWWBWBB 
UBWWWBU 
UWBBBWW 

4 

BBBB 
WWWB 
BWBB 
WWBU 

6 

WBWBUU 
BWBBUW 
UWBBBW 
UBBBUW 
UUUUBU 
WWBBUW 

10 

UUUUUUUUUU 
UUUUUUUUUU 
UUUUUUUUUU 
UUUUUUUUUU 
UUUUUUUUUU 
UUUUUUUUUU 
UUUUUUUUUU 
UUUUUUUUUU 
UUUUUUUUUU 
UUUUUUUUUU 

0
That's the output which I've gotten.

Code: Select all

White has a winning path.
Black has a winning path.
White can win in one move.
White has a winning path.
White can win in one move.
Black has a winning path.
Black can win in one move.
White has a winning path.
There is no winning path.
White has a winning path.
Black has a winning path.
There is no winning path.
White can win in one move.
White can win in one move.
White can win in one move.
Black can win in one move.
Black can win in one move.
Black has a winning path.
White can win in one move.
White has a winning path.
Black has a winning path.
Black can win in one move.
There is no winning path.

dvntae
New poster
Posts: 7
Joined: Fri Feb 14, 2003 12:50 pm

Post by dvntae »

do u use dfs, bfs? or other algorithm? posting the code might help ^.^ hehheheh

sERbU
New poster
Posts: 6
Joined: Thu Apr 08, 2004 10:06 am
Location: Barcelona

601 WA Why ??

Post by sERbU »

Hi. I'm getting WA for problem 601, but I don't know why. I tested my program against a reasonably large (and in my opinion complete) input/output combination, and my program gets everything right (newlines and so too). :cry:

I'd like to ask whether anybody minds giving me some sample input/output to test my program against, help is appreciated a lot, thanks!

sERbU
New poster
Posts: 6
Joined: Thu Apr 08, 2004 10:06 am
Location: Barcelona

I don't understand anything, why WA ??

Post by sERbU »

I'm going to suffer a heart attack. Socorro !!
Could anybody say me why I get always wrong answer ??

Code: Select all

#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool path_close(int i,int j,int N,bool found,vector<vector<pair<bool,char> > >& M,char c,string colour){

  if(!found && j==N-1 && M[i][j].second == c){
    M[i][j].first=true;
    cout << colour + " has a winning path." << endl;
    found = true;
  }
  else if(i>=0 && i<N && M[i][j].second==c && !M[i][j].first){
    M[i][j].first=true;
    if(i>0 && !M[i-1][j].first && M[i-1][j].second==c)  found=path_close(i-1,j,N,found,M,c,colour);
    if(i<N-1 && !M[i+1][j].first && M[i+1][j].second==c)  found=path_close(i+1,j,N,found,M,c,colour);
    if(j>0 && !M[i][j-1].first && M[i][j-1].second==c)  found=path_close(i,j-1,N,found,M,c,colour);
    if(j<N-1 && !M[i][j+1].first && M[i][j+1].second==c)  found=path_close(i,j+1,N,found,M,c,colour);
  }
  return found;
}

bool path_open(int i,int j,int N,int num_unfiled,bool found,vector<vector<pair<bool,char> > >& M,
        char c,string colour){

  M[i][j].first=true;
  if(M[i][j].second=='U') num_unfiled++;
  if(!found && j==N-1 && num_unfiled==1){
    if((M[i][j].second=='U' || M[i][j].second==c) && num_unfiled==1){
      cout << colour + " can win in one move." << endl;
      found=true;
    }
  }
  else if(j>0 && i>=0 && i<N  && num_unfiled<=1){

    M[i][j].first=true;

    if(j>0 && !M[i][j-1].first){
      if(M[i][j-1].second==c) found=path_open(i,j-1,N,num_unfiled,found,M,c,colour);
      else if(M[i][j-1].second=='U')  found=path_open(i,j-1,N,num_unfiled,found,M,c,colour);
    }
    if(j<N-1 && !M[i][j+1].first){
      if(M[i][j+1].second==c) found=path_open(i,j+1,N,num_unfiled,found,M,c,colour);
      else if(M[i][j+1].second=='U')  found=path_open(i,j+1,N,num_unfiled,found,M,c,colour);
    }
    if(i>0 && !M[i-1][j].first){
      if(M[i-1][j].second==c) found=path_open(i-1,j,N,num_unfiled,found,M,c,colour);
      else if(M[i-1][j].second=='U')  found=path_open(i-1,j,N,num_unfiled,found,M,c,colour);
    }
    if(i<N-1 && !M[i+1][j].first){
      if(M[i+1][j].second==c) found=path_open(i+1,j,N,num_unfiled,found,M,c,colour);
      else if(M[i+1][j].second=='U')  found=path_open(i+1,j,N,num_unfiled,found,M,c,colour);
    }
  }
  return found;
}

int main(){

  char box;
  int N_board;
  int k=0;
  bool found;

  cin >> N_board;
  cin.ignore();
  cin.ignore();

  while(N_board != 0){
    vector<vector<pair<bool,char> > > MW(N_board, vector<pair<bool,char> > (N_board));
    vector<vector<pair<bool,char> > > MB(N_board, vector<pair<bool,char> > (N_board));

    // Box in false, means that we haven't looked for path yet

    for(int i=0;i<N_board;i++){
      k=N_board-1;
      for(int j=0;j<N_board;j++){
        cin >> box;
        MW[i][j] = make_pair(false,box);
        MB[k][i] = make_pair(false,box);
        k--;
      }
    }

    // If N=1, we must treat the single case before

    if(N_board==1){
      if(MW[0][0].second=='W') cout << "White has a winning path." << endl;
      else if(MW[0][0].second=='B') cout << "Black has a winning path." << endl;
      else  cout << "White can win in one move." << endl;
      found=true;
    }
    else  found=false;

    // We are going to look for a path_close for whites
    for(int i=0;i<N_board;i++){
      if(!found){
        if(!MW[i][0].first && MW[i][0].second=='W'){
          MW[i][0].first=true;
          found=path_close(i,1,N_board,false,MW,'W',"White");
        }
      }
      else  i=N_board;
    }

    if(!found)
      for(int i=0;i<N_board;i++)
        for(int j=0;j<N_board;j++)
          MW[i][j].first = false;

    // We are going to look for a path_open for whites
    for(int i=0;i<N_board;i++){
      if(!found){
        if(!MW[i][0].first && MW[i][0].second=='W'){
          MW[i][0].first=true;
          found=path_open(i,1,N_board,0,false,MW,'W',"White");
        }
        else if(!MW[i][0].first && MW[i][0].second=='U'){
          MW[i][0].first=true;
          found=path_open(i,1,N_board,1,false,MW,'W',"White");
        }
      }
      else i=N_board;
    }

    // We are going to look for a path_close for blacks
    for(int i=0;i<N_board;i++){
      if(!found){
        if(!MB[i][0].first && MB[i][0].second=='B'){
          MB[i][0].first=true;
          found=path_close(i,1,N_board,false,MB,'B',"Black");
        }
      }
      else i=N_board;
    }

    if(!found)
      for(int i=0;i<N_board;i++)
        for(int j=0;j<N_board;j++)
          MB[i][j].first = false;

    // We are going to look for a path_open for blacks
    for(int i=0;i<N_board;i++){
      if(!found){
        if(!MB[i][0].first && MB[i][0].second=='B'){
          MB[i][0].first=true;
          found=path_open(i,1,N_board,0,false,MB,'B',"Black");
        }
        else if(!MB[i][0].first && MB[i][0].second=='U'){
          MB[i][0].first=true;
          found=path_open(i,1,N_board,1,false,MB,'B',"Black");
        }
      }
      else  i=N_board;
    }

    // There is no path neither whites nor blacks
    if(!found) cout << "There is no winning path." << endl;

    MW.clear();
    MB.clear();
    cin.ignore();
    cin >> N_board;
    cin.ignore();
    cin.ignore();
  }
}
This is my last attempt. If I don't become to solve it I think that I won't feel qualified for going on studying Computer Science. :cry:
Thank you.

cOsMo
New poster
Posts: 8
Joined: Fri Dec 10, 2004 11:04 pm
Location: Split , Croatia

601 WHY TLE?

Post by cOsMo »

Code: Select all

#include <cstdio>
#include <string>
#include <iostream>
#define MAX 81
using namespace std;

int dx[]={ 1,0,0,-1};
int dy[]={ 0,-1,1,0};
int bio[MAX][MAX];
char mat[MAX][MAX];
int n,sol=0;

int ok(int x,int y)
{
	if (x>=0 && x<n && y>=0 && y<n) return 1;
	return 0;
}
void dfs(int x,int y,int col,char c,int koliko)
{
	int i;
	if (sol>0) return;
	if (col==n-1) {
		if (koliko==0) {
			sol=1; 
			return; 
		}
		else  if (koliko==1) { 
			sol=2; 
			return;
		}
	}
	bio[x][y]=1;

	for (i=0;i<4;i++)
		if (bio[x-dx[i]][y-dy[i]]==0 && ok(x-dx[i],y-dy[i]))  {
				
				if		(c=='W') col=y-dy[i];	
				else if (c=='B') col=x-dx[i];	
				
				if      (mat[x-dx[i]][y-dy[i]]==c) 					dfs(x-dx[i],y-dy[i],col,c,koliko);
		    	else if (mat[x-dx[i]][y-dy[i]]=='U' && koliko==0) 	dfs(x-dx[i],y-dy[i],col,c,koliko+1);
		}
	bio[x][y]=0;
}

int main(void)
{
	string a;
	int i,j;
	for (;;)
	{
	scanf("%d",&n);	if (n==0) break;
	
		for (i=0;i<n;i++) {
			cin>>a;
			int duz=a.size();
			for (j=0;j<duz;j++) {
				mat[i][j]=a[j];
				bio[i][j]=0;
			}	
		}
	
	for (i=0;i<n;i++)	
	{
			sol=0;
			if (mat[i][n-1]=='W')	{
			dfs(i,0,0,'W',0);
			if		(sol==1) { printf("White has a winning path.\n"); break; }
			else if (sol==2) { printf("White can win in one move.\n");break;}
			}
			else if (mat[i][0]=='U' && sol==0) 	{
			dfs(i,0,0,'W',1);
			if (sol==2) {printf("White can win in one move.\n"); break;}
			}
	}

	if (sol==0)
	for (i=0;i<n;i++)	{
		if (mat[0][n-1]=='B')	{
		dfs(i,0,0,'B',0);
		if		(sol==1) { printf("Black has a winning path.\n"); break;}
		else if (sol==2) { printf("Black can win in one move.\n");break;}
		}
		if (mat[0][1]=='U' && sol==0) {
			dfs(0,i,0,'B',1);
			if (sol==2) {printf("Black can win in one move.\n"); break;}
		}
	}
	
	if (sol==0) printf("There is no winning path.\n");
	

	}
return 0;
}
[/code]

SHAHADAT
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh

painfull rte

Post by SHAHADAT »

if any one have any critical inputs.
i have getting wa.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish »

>>SHAHADAT

if u check all the cases posted in this thread i think it's enough. though u get WA better u should think about ur algorithm.

try this cases also
Input

Code: Select all

4
BUBB
WBBW
UBUU
BBBB

3
BWW
WBB
UUU

5
BBBBB
WWWWU
UUUUB
BBBBB
BBBBB
Output

Code: Select all

Black has a winning path.
There is no winning path.
White can win in one move.

kogorman
New poster
Posts: 14
Joined: Sat Dec 02, 2006 6:58 am

601 - The Path - a clarification

Post by kogorman »

I just had an email exchange with carlos, and this explained an oddity in the problem description. There is a missing comma in the phrase explaining "adjacent". It should read
" ... if one is immediately to the left, to the right, above, or below the other"
.
Without the second comma in that phrase, I was thinking that there was one diagonal connection that was valid.

Maybe I'll be able to solve it now.

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 601 - The Path

Post by Jehad Uddin »

Getting WA in this problem pls help :oops: :oops:

Code: Select all

#include<iostream>
#include<queue>
#include<string>
#include<math.h>
#include<vector>
#include<map>

using namespace std;

struct ss
{
    int x,y;
    int cost,st;
};

int N;
int fn;
string grid[100];
int dis[100][100];
int color[100][100];
int inx[]={0,0,1,-1};
int iny[]={1,-1,0,0};

void ini()
{
    int i,j;
    for(i=0;i<=N;i++)
        for(j=0;j<=N;j++)
            color[i][j]=0;
}

void flood(int x,int y,int k,int w)
{
    int i,j,u,v;
    if(w==1&&y==N-1&&k==1&&grid[x][y]=='W')
    {
        fn=1;
    }
    if(w==2&&x==N-1&&k==3&&grid[x][y]=='B')
    {
        fn=3;
    }
    for(i=0;i<4;i++)
    {
        u=inx[i]+x,v=iny[i]+y;
        if(u>=0&&u<=N-1&&v>=0&&v<=N-1)
        {
            if(grid[u][v]==grid[x][y]&&color[u][v]!=k)
            {
                color[u][v]=k;
                flood(u,v,k,w);
            }
        }
    }

}

int main()
{
    int i,j,k,l;
    int cnt1=0,cnt2=0,u,v;
    while(scanf("%d",&N)==1&&N)
    {
        ini();

        for(i=0;i<N;i++) cin>>grid[i];


        fn=0;
        for(i=0;i<N;i++)
        {
            if(grid[i][0]=='W'&&color[i][0]==0)
            {
                color[i][0]=1;
                flood(i,0,1,1);
            }
        }
        if(fn==1)
        {
            cout<<"White has a winning path."<<endl;
        }
        else
        {
            for(i=0;i<N;i++)
            {
                if(grid[i][N-1]=='W'&&color[i][N-1]==0)
                {
                    color[i][N-1]=2;
                    flood(i,N-1,2,1);
                }
            }
            
            for(i=0;i<N;i++)
            {
                for(j=0;j<N;j++)
                {
                    if(grid[i][j]=='U')
                    {
                        cnt1=0,cnt2=0;
                        for(k=0;k<4;k++)
                        {
                            u=i+inx[k],v=j+iny[k];
                            if(u>=0&&u<N&&v>=0&&v<N)
                            {
                                if(color[u][v]==1) cnt1++;
                                if(color[u][v]==2) cnt2++;
                            }

                        }
                        if(cnt1&&cnt2)  fn=2;
                        if(cnt2&&j==0) fn=2;
                        if(cnt1&&j==N-1) fn=2;
                    }
                }
            }
            if(fn==2)  cout<<"White can win in one move."<<endl;

        }

        if(fn==0)
        {
            for(i=0;i<N;i++)
            {
                if(color[0][i]!=3&&grid[0][i]=='B')
                {
                    color[0][i]=3;
                    flood(0,i,3,2);
                }
            }
            if(fn==3) cout<<"Black has a winning path."<<endl;
            if(fn!=3)
            {
                for(i=0;i<N;i++)
                {
                    if(color[N-1][i]!=4&&grid[N-1][i]=='B')
                    {
                        color[N-1][i]=4;
                        flood(N-1,i,4,2);
                    }
                }
                for(i=0;i<N;i++)
                {
                    for(j=0;j<N;j++)
                    {
                        if(grid[i][j]=='U')
                        {
                            cnt1=0,cnt2=0;
                            for(k=0;k<4;k++)
                            {
                                u=i+inx[k],v=j+iny[k];
                                if(u>=0&&u<N&&v>=0&&v<N)
                                {
                                    if(color[u][v]==3) cnt1++;
                                    if(color[u][v]==4) cnt2++;
                                }

                            }
                            if(cnt1&&cnt2)  fn=4;
                            if(cnt2&&i==0) fn=4;
                            if(cnt1&&i==N-1) fn=4;
                        }
                    }
                }
                if(fn==4) cout<<"Black can win in one move."<<endl;
                else cout<<"There is no winning path."<<endl;

            }

        }


    }


    return 0;
}

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

WA........

Post by mahade hasan »

cuttttttttttttttttttt
Last edited by mahade hasan on Mon Nov 12, 2012 6:02 pm, edited 1 time in total.
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: 601 - The Path

Post by brianfry713 »

Input:

Code: Select all

4

WWUB
UWUW
WWBU
WBBU

0
AC output:

Code: Select all

White can win in one move.
Check input and AC output for thousands of problems on uDebug!

muneeb
New poster
Posts: 4
Joined: Wed Dec 26, 2012 3:05 pm

The path

Post by muneeb »

#include<iostream>
#include<string>
using namespace std;
int pathVisit();
int size;
char **path;
int **ref;
int ret;
int pathVisit()
{
for(int i=0;i<size;i++)
{
if(ref[size-1]==1 && ref[0]==1)
{
ret=1;
return ret;
}
if(ref[size-1]==1 && ref[0]==0) //U W
{
if(i==size-1)
{
if(ref[1]==1 || ref[i-1][0]==1 )
{
ret=2;
return ret;
}
}else if(i==0)
{
if(ref[i+1][0]==1 || ref[1]==1)
{
ret=2;
return ret;
}
}
else
{
if(ref[i+1][0]==1 || ref[1]==1 || ref[i-1][0]==1 )
{
ret=2;
return ret;
}
}
}
if(ref[0]==1 && ref[size-1]==0) //W U
{
if(i==0)
{
if(ref[i+1][size-1]==1 || ref[size-2]==1 )
{
ret=3;
return ret;
}
}
else if(i==size-1)
{
if( ref[i][size-2]==1 || ref[i-1][size-1]==1)
{
ret=3;
return ret;
}
}
else
{
if(ref[i+1][size-1]==1 || ref[i][size-2]==1 || ref[i-1][size-1]==1)
{
ret=3;
return ret;
}
}
}
}
for(int i=0;i<size;i++)
{
if(ref[size-1][i]==2 &&ref[0][i]==2)
{
ret=4;
return ret;
}
if(ref[size-1][i]==2 && ref[0][i]==0)
{
if(ref[0][i-1]==2 || ref[1][1]==2 || ref[0][i+1]==2)
{
ret=5;
return ret;
}
}
if(ref[size-1][i]==0 && ref[0][i]==2)
{
if(ref[size-1][i-1]==2 || ref[size-1][i+1]==2 || ref[size-2][i]==2 )
{
ret=6;
return ret;
}
}
}
return 0;
}
int main()
{
string input;
do
{
cin>>size;cout<<endl;
if(size==0)
{
break;
}
path=new char*[size];
for(int i=0;i<size;i++)
{
path[i]=new char[size];
}
ref=new int*[size];
for(int i=0;i<size;i++)
{
ref[i]=new int[size];
}
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
ref[i][j]=0;
}
}
for(int i=0;i<size;i++)
{
cin>>input;
int length=input.size();
for(int j=0;j<size;j++)
{
path[i][j]=input[j];
if(input[j]=='W')
{
ref[i][j]=1;
}
else if(input[j]=='B')
{
ref[i][j]=2;
}
else
{
ref[i][j]=0;
}
}
}
int t;
t=pathVisit();
while(1)
{
if(t==0)
{
cout<<"There is no winning path."<<endl;
break;
}
else if(t==1)
{
cout<<"White has winning path."<<endl;
break;
}
else if(t==2)
{
cout<<"White can win in one move."<<endl;
break;
}
else if(t==3)
{
cout<<"White can win in one move."<<endl;
break;
}
else if(t==4)
{
cout<<"Black has winning path."<<endl;
break;
}
else if(t==5)
{
cout<<"Black can win in one move."<<endl;
break;
}
else if(t==6)
{
cout<<"Black can win in one move."<<endl;
break;
}
else
{
cout<<"There is no winning path."<<endl;
break;
}
}
}while(1);
}

muneeb
New poster
Posts: 4
Joined: Wed Dec 26, 2012 3:05 pm

The path

Post by muneeb »

#include<iostream>
#include<string>
using namespace std;
int pathVisit();
int size;
char **path;
int **ref;
int ret;
int pathVisit()
{
for(int i=0;i<size;i++)
{
if(ref[size-1]==1 && ref[0]==1)
{
ret=1;
return ret;
}
if(ref[size-1]==1 && ref[0]==0) //U W
{
if(i==size-1)
{
if(ref[1]==1 || ref[i-1][0]==1 )
{
ret=2;
return ret;
}
}else if(i==0)
{
if(ref[i+1][0]==1 || ref[1]==1)
{
ret=2;
return ret;
}
}
else
{
if(ref[i+1][0]==1 || ref[1]==1 || ref[i-1][0]==1 )
{
ret=2;
return ret;
}
}
}
if(ref[0]==1 && ref[size-1]==0) //W U
{
if(i==0)
{
if(ref[i+1][size-1]==1 || ref[size-2]==1 )
{
ret=3;
return ret;
}
}
else if(i==size-1)
{
if( ref[i][size-2]==1 || ref[i-1][size-1]==1)
{
ret=3;
return ret;
}
}
else
{
if(ref[i+1][size-1]==1 || ref[i][size-2]==1 || ref[i-1][size-1]==1)
{
ret=3;
return ret;
}
}
}
}
for(int i=0;i<size;i++)
{
if(ref[size-1][i]==2 &&ref[0][i]==2)
{
ret=4;
return ret;
}
if(ref[size-1][i]==2 && ref[0][i]==0)
{
if(ref[0][i-1]==2 || ref[1][1]==2 || ref[0][i+1]==2)
{
ret=5;
return ret;
}
}
if(ref[size-1][i]==0 && ref[0][i]==2)
{
if(ref[size-1][i-1]==2 || ref[size-1][i+1]==2 || ref[size-2][i]==2 )
{
ret=6;
return ret;
}
}
}
return 0;
}
int main()
{
string input;
do
{
cin>>size;cout<<endl;
if(size==0)
{
break;
}
path=new char*[size];
for(int i=0;i<size;i++)
{
path[i]=new char[size];
}
ref=new int*[size];
for(int i=0;i<size;i++)
{
ref[i]=new int[size];
}
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
ref[i][j]=0;
}
}
for(int i=0;i<size;i++)
{
cin>>input;
int length=input.size();
for(int j=0;j<size;j++)
{
path[i][j]=input[j];
if(input[j]=='W')
{
ref[i][j]=1;
}
else if(input[j]=='B')
{
ref[i][j]=2;
}
else
{
ref[i][j]=0;
}
}
}
int t;
t=pathVisit();
while(1)
{
if(t==0)
{
cout<<"There is no winning path."<<endl;
break;
}
else if(t==1)
{
cout<<"White has winning path."<<endl;
break;
}
else if(t==2)
{
cout<<"White can win in one move."<<endl;
break;
}
else if(t==3)
{
cout<<"White can win in one move."<<endl;
break;
}
else if(t==4)
{
cout<<"Black has winning path."<<endl;
break;
}
else if(t==5)
{
cout<<"Black can win in one move."<<endl;
break;
}
else if(t==6)
{
cout<<"Black can win in one move."<<endl;
break;
}
else
{
cout<<"There is no winning path."<<endl;
break;
}
}
}while(1);
}

Post Reply

Return to “Volume 6 (600-699)”