I'm going to suffer a heart attack. Socorro !!
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.
Thank you.
