10284 - Chessboard in FEN

[stcheung]

Hi. For some reasons my code gets me a WA. I don't expect anyone to read my code below, but if someone has a set of test cases can he/she try them with my code and let me know what tests my program is failing?
That would be so much help. Thanks in advance!

Code: Select all

#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <ctype.h>

const int OCCUPIED = 5;
const int ATTACKED = 10;

int main()
{
  string input;
  while(true)
  {
    cin >> input;
    int board[22][22];
    for(int i=7; i<15; i++)
    {
       for(int j=7; j<15; j++)
         board[i][j] = 0;
    }
    int row=7, col=7;
    char piece;
    if(cin.eof())
      break;

    for(int i=0; i<input.length(); i++)
    {
      piece = input[i];
      if(piece >= '0' && piece <= '9')
      {
        col+=(piece - '0');
      }
      else if(piece == '/')
      {
        row++;
        col = 7;
      }
      else
      {
        board[row][col] = OCCUPIED;
        col++;
      }
    }

    row = col = 7;
    for(int i=0; i<input.length(); i++)
    {
      piece= tolower(input[i]);
      if(piece >= '0' && piece <= '9')
      {
        col+=(piece - '0');
      }
      else if(piece == '/')
      {
        row++;
        col = 7;
      }
      else
      {
        if(piece == 'k')
        {
          for(int j=-1; j<=1; j++)
          {
            for(int k=-1; k<=1; k++)
            {
              if(board[row+j][col+k] != OCCUPIED)
                board[row+j][col+k] = ATTACKED;
            }
          }
        }
        else if(piece == 'q')
        {
//          cout << "queen\ti:" << row-7 << "\tj: " << col-7 << "\n";

          // HORIZONTAL & VERTICAL
          for(int k=1; k<=7; k++)
          {
            if(board[row-k][col] == OCCUPIED)
              break;
            board[row-k][col] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row+k][col] == OCCUPIED)
              break;
            board[row+k][col] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row][col-k] == OCCUPIED)
              break;
            board[row][col-k] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row][col+k] == OCCUPIED)
              break;
            board[row][col+k] = ATTACKED;
          }
          // DIAGONAL
          for(int k=1; k<=7; k++)
          {
            if(board[row+k][col+k] == OCCUPIED)
              break;
            board[row+k][col+k] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row-k][col-k] == OCCUPIED)
              break;
            board[row-k][col-k] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row-k][col+k] == OCCUPIED)
              break;
            board[row-k][col+k] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row+k][col-k] == OCCUPIED)
              break;
            board[row+k][col-k] = ATTACKED;
          }
        }
        else if(piece == 'r')
        {
          for(int k=1; k<=7; k++)
          {
            if(board[row-k][col] == OCCUPIED)
              break;
            board[row-k][col] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row+k][col] == OCCUPIED)
              break;
            board[row+k][col] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row][col-k] == OCCUPIED)
              break;
            board[row][col-k] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row][col+k] == OCCUPIED)
              break;
            board[row][col+k] = ATTACKED;
          }
        }
        else if(piece == 'b')
        {
          for(int k=1; k<=7; k++)
          {
            if(board[row+k][col+k] == OCCUPIED)
              break;
            board[row+k][col+k] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row-k][col-k] == OCCUPIED)
              break;
            board[row-k][col-k] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row-k][col+k] == OCCUPIED)
              break;
            board[row-k][col+k] = ATTACKED;
          }
          for(int k=1; k<=7; k++)
          {
            if(board[row+k][col-k] == OCCUPIED)
              break;
            board[row+k][col-k] = ATTACKED;
          }
        }
        else if(piece == 'n')
        {
          if(board[row-2][col-1] != OCCUPIED)
            board[row-2][col-1] = ATTACKED;
          if(board[row-2][col+1] != OCCUPIED)
            board[row-2][col+1] = ATTACKED;
          if(board[row-1][col-2] != OCCUPIED)
            board[row-1][col-2] = ATTACKED;
          if(board[row-1][col+2] != OCCUPIED)
            board[row-1][col+2] = ATTACKED;
          if(board[row+2][col-1] != OCCUPIED)
            board[row+2][col-1] = ATTACKED;
          if(board[row+2][col+1] != OCCUPIED)
             board[row+2][col+1] = ATTACKED;
          if(board[row+1][col-2] != OCCUPIED)
            board[row+1][col-2] = ATTACKED;
          if(board[row+1][col+2] != OCCUPIED)
            board[row+1][col+2] = ATTACKED;
        }
        else if(piece == 'p')
        {
          if(input[i] == 'p')
          {
            if(board[row+1][col-1] != OCCUPIED)
              board[row+1][col-1] = ATTACKED;
            if(board[row+1][col+1] != OCCUPIED)
              board[row+1][col+1] = ATTACKED;
          }
          else
          {
            if(board[row-1][col-1] != OCCUPIED)
              board[row-1][col-1] = ATTACKED;
            if(board[row-1][col+1] != OCCUPIED)
              board[row-1][col+1] = ATTACKED;
          }
        }
           
      col++;
      }
    }


    int numsquares = 0;
    for(int i=7; i<15; i++)
    {
        for(int j=7; j<15; j++)
        {
          if(board[i][j] != OCCUPIED && board[i][j] != ATTACKED)
          {
            numsquares++;
//            cout << "i: " << i-7 << "\tj: " << j-7 << "\n";
          }
        }
    }
    cout << numsquares << "\n";
  }
  return 0;
}

[Dmytro Chernysh]

Well, the problem is not that difficult, but it does contain some tricks...
I can give you my Pascal code. Mail me...

[hackfox]

Note pawn doesn't attack piece in front of it. It attacks piece in left/right
front of it.

[dootzky]

funny thing is, i solved similar problem, p10196 "Check The Check".

this is how i handle this problem:

1) i read one line of input
2) then i process it like this
- if (some_of_the_figures) put_the_piece_on_the_board;
- else if ("/") put_me_in_one_row_below_and_set_column-counter=0;
- else (NUMBER N) put N "." on_the_table;
3) when i have filled table (which works, 100%, i checked output of the chess table on many inputs, including problem sample input), i go through a long function "white_attack()", and then "black_attack()", where i have this "int array[8][8]", which is initialized and filled with "0".
4) now i simply go through the filled chess table, and if a figure is found, attack where it should attack. i used the very SAME algorithm as in problem p10196 (for which i got ACC).
5) i mark every place in "int array" with number "1" if it is attacked or occupied.
6) finally, i simply count the number of "0" in my "int array[8][8]", and that's the result.

it works on both sample inputs for the problem, but i'm getting WA???
why?

any tricks? did i misunderstood the problem? it says:

you are asked to compute the number of unoccupied squares on the board which are not attacked by any piece.

i will post my BIG BIG BIG code below this post, so you can maybe see my mistake (but everything SEEMS to work, i don't see where's the error).

thx for tha' time,
dootzky

[dootzky]

Code: Select all

code removed after ACC...

[dootzky]

i must say - i'm very impressed how many of you replyed on my question.

anyway, i found my own error. it was naive, ofcourse.
the similar problem i mentioned, p10196, was all about these conditions:

1) if the white king is in check
2) if the black king is in check
3) if none of them is in check

but surely you notice, that in chess, king can NOT "check" the other king. in other words, my algorithm was perfect, for the first problem. then when i copy/pasted the "attack" algo from my first program, i forgot just one small detail:

- in chess - king DOES attack 8 possitions around him self, while occupying his own square.
so, in this problem p10284, i should've watch out for the 'kings attack', because it's not really importan if "king can check the other king", and that was my mistake.

i hope i helped somebody with all these posts.
best regards to future readers (and the old ones, ofcourse)
dootzky

[dootzky]

it was kind a fun talking with my self, actually!

i'm a gonna go talk to notepad for a while now..

just messing with ya all,
respect,
dootzky

[dootzky]

i fried my brain with this problem, and i hope this hint helps:

http://online-judge.uva.es/board/viewto ... 4674#34674

that's my own post there, i was talking to myself! and got ACC, ofcourse!

but, about your program:

- it seems to me that you don't initialize ALL the 'squares' of your board:

Code: Select all

for(int i=7; i<15; i++) 
{ 
for(int j=7; j<15; j++) 
board[i][j] = 0; 
} 

but later in your algorithm, you freely ask for it's value:

Code: Select all

if(board[row-2][col-1] != OCCUPIED) 
board[row-2][col-1] = ATTACKED; 

maybe there's some error in that.
i sent your code, unaltered, and then altered, and there WAS some result. i mean - your program ran a little bit longer, so it means it maybe got a few more test cases correct, and then failed somewhere.

and one more hint:
- you use OCCUPIED and ATTACKED for you detection of free squares.
i used something much more simpler. one 2D integer array (int array[20][20]) which was initialized by '0'.

then, i read the input.
for every figure that i read, i mark on that square a '1' in my int array (that means OCCUPIED). later in my code, when go through 'attacking procedure', i also mark 'attacked' squares with '1'.
and on the end, i simply cound number of '0' and print them.
ofcoruse, i could mark OCCUPIED with '5' or anything else, and ATTACKED with '9' or whatever, but it's not important.
what's important is that field is no longer our 'square of interest'.

hope i helped, at least a little,
regards, and i wish you good luck, your code is pretty much correct, as for i can say,
dootzky

[plamplam]

May be this will help somebody:

Code: Select all

8/8/8/8/3b4/8/8/8
8/8/8/8/3B4/8/8/8
8/8/8/8/3r4/8/8/8
8/8/8/8/3R4/8/8/8
8/8/8/8/3q4/8/8/8
8/8/8/8/3Q4/8/8/8
8/8/8/8/3n4/8/8/8
8/8/8/8/3N4/8/8/8
8/8/8/8/3k4/8/8/8
8/8/8/8/3K4/8/8/8
8/8/8/8/3p4/8/8/8
8/8/8/8/3P4/8/8/8

Code: Select all

50
50
49
49
36
36
55
55
55
55
61
61

Just handle the pawns carefully and remember bishops/rooks/queens can't attack through a piece.

[dibery]

Input:

Code: Select all

8/8/8/3Q4/3N4/8/8/8
8/8/8/8/7B/6N1/8/7R
8/8/8/8/1p1p1p2/8/P1P1P1P1/8
5k1r/2q3p1/p3p2p/1B3p1Q/n4P2/6P1/bbP2N1P/1K1RR3
8/8/8/8/8/8/8/7r
rrrrrrrr/8/8/8/8/8/8/8
1n1n1n1n/n1n1n1n1/1n1n1n1n/n1n1n1n1/1n1n1n1n/n1n1n1n1/1n1n1n1n/n1n1n1n1
n7/8/8/8/8/8/8/7N
Q7/8/8/8/8/8/8/8
Qp6/PP6/8/8/8/8/8/8
Kp6/PP6/8/8/8/8/8/8
Bp6/PP6/8/8/8/8/8/8
Np6/PP6/8/8/8/8/8/8

Output:

Code: Select all

37
44
49
3
49
0
0
58
42
58
58
58
57

[HuyTranQ]

I get WA but don't know where I get it wrong. I passed all the test from uDebug and above but still got it WA.
Can you guys have a look at my code? Thank you very much!!!

Code: Select all

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::getline;

struct SpecialPiece
{
	char c;
	int a , b;
	SpecialPiece()
	{

	}
	SpecialPiece(char c , int a , int b) : c(c) , a(a) , b(b)
	{

	}
};

bool isBlack;
string line;
char c;
int length , row , col , result;
bool chessBoard[8][8] , occupiedBoard[8][8];
vector<SpecialPiece> listPiece;


void checkPawn();
void checkRook();
void checkKnight();
void checkBishop();
void checkKing();
void checkSquare(int a, int b);

void print()
{
	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
			cout << chessBoard[i][j] << ' ';
		cout << endl;
	}
}

int main()
{
	while (true)
	{
		getline(cin , line);
		length = line.size();
		if (length == 0)
			break;
		row = 0;
		col = 0;
		result = 64;
		listPiece.resize(0);
		for (int i = 0; i < 8; ++i)
			for (int j = 0; j < 8; ++j)
			{
				chessBoard[i][j] = false;
				occupiedBoard[i][j] = false;
			}
		for (int i = 0; i < length; ++i)
		{
			c = line[i];
			if ('0' < c && c < '9')
				col += c - '0';
			else
			{
				if ('a' < c && c < 'z')
				{
					c -= 32;
					isBlack = true;
				}
				else
					isBlack = false;
				switch (c)
				{
					case 'P':
						checkPawn();
						break;
					case 'N':
						checkKnight();
						break;
					case 'K':
						checkKing();
						break;
					case 'R':
					case 'B':
					case 'Q':
						listPiece.push_back(SpecialPiece(c , row , col));
						break;
					default:
						++row;
						col = 0;
						continue;
				}
				checkSquare(row , col);
				occupiedBoard[row][col] = true;
				++col;
			}
		}
		length = listPiece.size();
		for (int i = 0; i < length; ++i)
		{
			row = listPiece[i].a;
			col = listPiece[i].b;
			switch (listPiece[i].c)
			{
				case 'R':
					checkRook();
					break;
				case 'B':
					checkBishop();
					break;
				case 'Q':
					checkRook();
					checkBishop();
					break;
				default:
					break;
			}
		}
		cout << result << endl;
	}
	return 0;
}

void checkSquare(int a , int b)
{
	if (!chessBoard[a][b])
	{
		--result;
		chessBoard[a][b] = true;
	}
}

void checkPawn()
{
	int newRow = row + ((isBlack) ? 1 : -1);
	if (0 <= newRow && newRow < 8)
	{
		if (col > 0)
			checkSquare(newRow , col - 1);
		if (col < 7)
			checkSquare(newRow, col + 1);
	}
}

void checkRook()
{
	static int offsetX[] = { -1 , 0 , 1 , 0 };
	static int offsetY[] = { 0 , -1 , 0 , 1 };
	int a , b;
	for (int i = 0; i < 4; ++i)
		for (int j = 1; j < 8; ++j)
		{
			a = row + offsetX[i] * j;
			b = col + offsetY[i] * j;
			if (a < 0 || a > 7 || b < 0 || b > 7 ||
				occupiedBoard[a][b])
				break;
			checkSquare(a , b);
		}
}

void checkKnight()
{
	int a , b;
	static int offset[] = { 1 , 2 };
	static int coef[] = { -1 , 1 };
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
			{
				a = row + coef[j] * offset[i];
				b = col + coef[k] * offset[(i + 1) % 2];
				if (a < 0 || a > 7 || b < 0 || b > 7)
					continue;
				checkSquare(a , b);
			}
}

void checkBishop()
{
	static int offsetX[] = { -1 , -1 , 1 , 1 };
	static int offsetY[] = { -1 , 1 , -1 , 1 };
	int a , b;
	for (int i = 0; i < 4; ++i)
		for (int j = 1; j < 8; ++j)
		{
			a = row + offsetX[i] * j;
			b = col + offsetY[i] * j;
			if (a < 0 || 7 < a || b < 0 || 7 < b ||
				occupiedBoard[a][b])
				break;
			checkSquare(a , b);
		}
}

void checkKing()
{
	static int offset[3] = { -1 , 0 , 1 };
	int a , b;
	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j)
		{
			a = row + offset[i];
			b = col + offset[j];
			if (a < 0 || 7 < a ||
				b < 0 || 7 < b)
				break;
			checkSquare(a , b);
		}
			
}

[milesstevenson]

Could anyone help me understand what I could be doing wrong in my code? It's a bit verbose, but as far as I understand I pass every test case.
Edit: Nvm AC

Code: Select all

// AC