Need help with a programming contest exercise

[Mastaron]

Hi everybody,
I signed up for a contest, and I'm practicing, but now i'm a little blocked with this.

The Problem:

There is a game with an N*N matrix, every element is a character or a digit. The object is to delete the most elements.

Removing an element: select an element which has a neighbor vertical or horizontal but not diagonal. The neighbor must be the same character as the selected element. You delete both the selected element and all of it's neighbors (mustn't delete neighbors' neighbors). After the removal, the elements above the deleted elements in a column goes down, and if a column is empty, the columns from the left move to the right to fill the blank column.

It's required to write a program which deletes the maximum possible elements.

Input:
The input file contains more test. Every test has in the 1st line an integer N (2<=N<=5). The next N rows contains N elements. The file ends with a line containing 0.

Output:
The output file contains for every test a line, the number of elements remained in the matrix after deleting the maximum possible elements.

Input file:

3
aab
aab
bcc
3
aba
bbb
aba
3
abd
bbb
cbe
4
1aa2
b21b
b12b
2bb1
4
aaaa
bbbb
bbcb
bbbb
4
acbg
aceg
bdfh
bdfh
4
edbd
faae
gaae
dbcc
4
aacc
aacc
bbdd
bbdd
5
adfhk
adfhk
bexil
begil
ccgjj
5
edbdf
adbde
caaea
baaec
ggccb
5
aaaaa
abaca
acaba
abaca
aaaaa
0

Output file:

0
0
4
0
1
1
3
2
1
1
1

Output file for my program (4/10):

1
0
4
1
1
2
8
0
1
9
6

My code is wrong because I delete the neighbors' neighbors

My code:

#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("D.in");
ofstream g ("D.out");
char a[6][6];
short n,ch;

void cdel(short x, short y){ //deletes the element and all of it's neighbors
    char z=a[x][y];          //including the neighbors' neighbors
    a[x][y]='-';
    ch--;
    if(y>1&&a[x][y-1]==z)
        cdel(x,y-1);
    if(y<n&&a[x][y+1]==z)
        cdel(x,y+1);
    if(x<n&&a[x+1][y]==z)
        cdel(x+1,y);
    if(x>1&&a[x-1][y]==z)
        cdel(x-1,y);
}

void rccheck(){ // copies the elements of a column from up to down, columns from left to right
    for(short i(1);i<=n;i++){
        bool col=false;
        short x=n;
        while(a[x][i]!='-'&&x>1)
            x--;
        if(x==1  && a[x][i]=='-' && a[x+1][i]=='-')
            col=true;
        if(col){
            if(i>1)
                for(short l=1;l<=n;l++){
                    for(short k=i;k>=2;k--)
                        a[l][k]=a[l][k-1];
                    a[l][1]='-';
            }
        } else{
            for(short j=x-1;j>=1;j--){
                if(a[j][i]!='-'){
                    a[x][i]=a[j][i];
                    a[j][i]='-';
                    x--;
                }
            }
        }
    }
}

bool ccheck(short x, short y){ //True if has min 1 neighbor
    char z=a[x][y];
    bool big=false;
    if(y>1&&a[x][y-1]==z)
        big=true;
    if(y<n&&a[x][y+1]==z)
        big=true;
    if(x<n&&a[x+1][y]==z)
        big=true;
    if(x>1&&a[x-1][y]==z)
        big=true;
    return big;
}


void joc(){
    for(short i=1;i<=n;i++)  // I delete the elements in order because I
    for(short j=1;j<=n;j++){ // don't know how can i choose which to delete first
        if(a[i][j]!='-')     // I need help here
            if(ccheck(i,j)){
                cdel(i,j);
                rccheck();
        }
    }
    g<<ch<<endl;
}

int main()
{
    do{ //reading the file for every tests
        f>>n;
        ch=n*n;
        for(short i=1;i<=n;i++)
            for(short j=1;j<=n;j++)
                f>>a[i][j];
        if(n)
            joc();

    }while(n!=0);

    f.close(); g.close();
    return 0;
}

Example:

aab
aab
bcc

delete (3,2)

a--
aab
bab

delete (3,2)

-a-
-ab
-bb

delete (2,2)

---
--b
-bb

delete (3,3)

---
---
---

So as you see, I have to find a way to choose which element to delete first. Like in candy crush. Can you help me?

Notes:

· You can delete a neighbor only if it's the same character as the selected character (whose neighbor it is)
· You can only delete the neighbors, can't delete the neighbor's neighbors. So i have to rewrite this code.
· I translated the exercise from Romanian (neither are my native language), so I've probably made some mistakes.

Thank you,
Mastaron

[ne555]

> I'm not sure if i have to delete the neighbors's neighbors, or just the
> element &neighbors.
iirc, you delete the neighbours of the selected element.
At most 5 elements would be deleted, and they can be anything.

Although that was based on your translation, so...

> But as you see in the 1st example, if you don't delete the neighbor's
> neighbors, there will remain a lonely "a".

aab
aab
bcc

select (0,0)

..b
.ab
bcc

select (0,2)

...
.a.
bcc

select (2,1)

...
...
...

> I don't understand the last example

aaaaa
abaca
acaba
abaca
aaaaa

if you select (2,0) then you'll have

aaaaa    ..aaa
.baca    .aaca
..aba -> .baba
.baca    abaca
aaaaa    aaaaa

so you put together the `b'. A similar thing can be done with the `c' by selecting (2,4)
Then you can delete the `b' and `c' and you'll have a board with just `a'.
It remains to see i you can delete all those `a', or there will be one remaining.

[Mastaron]

I translated bad, sorry. You can only delete the neighbors if they are the same character as the selected

eg.
delete (0,1)

aba     a-a
cbf     c-f     
ada     ada

[ne555]

aab
aab
bcc

select (2,2)

aab    a..
aab -> aab
b..    bab

select(0,0)

...
.ab
bab

select(2,1)

...    ...
..b -> ..b
b.b    .bb

select(2,2)

...
...
...

[dhayden]

You can avoid deleting the neighbors' neighbors by changing lines 15-22 to:

    if(y>1&&a[x][y-1]==z)
        a[x][y-1] = '-';
    if(y<n&&a[x][y+1]==z)
        a[x][y+1] = '-';
    if(x<n&&a[x+1][y]==z)
        a[x+1][y] = '-';
    if(x>1&&a[x-1][y]==z)
        a[x-1[y] = '-';

There's a trick that will let you avoid all those boundary checks. Since you're already using indexes 1 - n instead of 1 - n-1, just make the board one square larger and put '-' in those positions.

       -----
aab    -aab-
aab -> -aab-
bcc    -bcc-
       -----

Here the zero'th row/column contain '-', as well as the (n+1)'th. Note that you'll have to expand array a to 7x7

l is a really bad choice for a variable name because it's so easy to mistake it for 1.

ccheck will return true when a blank cell has a blank neighbor.

Regarding how to determine the minimum number of moves, one way is to make a copy of the board and see many moves it takes to clear the copy. To do this, you should probably create a class for the board and turn most of your functions into class members.