## 10189 - Minesweeper

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

Moderator: Board moderators

grirus
New poster
Posts: 12
Joined: Sat Mar 13, 2004 6:15 pm
Location: Sampa - Brazil
Contact:
Hey man... your code is so confused to me.... but i give a sugestion to you.....

- Create a char matrix with 100x100..
- inicialize all positions with '0'...
- read the input placed * in positions and don
thanx

mattapayne
New poster
Posts: 8
Joined: Thu Jun 17, 2004 5:50 am
OK, thanks for the suggestions.

Maybe I'm reading the problem incorrectly. As I understand it, I'm supposed to allow input of any number of "fields" and when 0 0 is entered for field n, m, terminate. Then print all entered "fields" with proper numeric conversion.

My solution is to create a 2d char array for each field and store it in a struct, along with n, m values. Then I add this struct to a vector.

To print out the fields, I can loop through each item in the vector and call a print funtion on it.

But maybe I'm looking at it wrong ... should I be adding all inputs to the same array? That just doesn't make sense to me. The columns would have a maximum of 100 characters, but the number of available rows would be dependant on user input.

Could anyone clarify this for me so that I can move on without going insane?

Thanks.

grirus
New poster
Posts: 12
Joined: Sat Mar 13, 2004 6:15 pm
Location: Sampa - Brazil
Contact:
You only count how many bombs are in the adjacense of a security point..

example: *.*
answer: *2*

Read my algoritm and make you source....

Test this inputs and try submit.... Remeber '0' +1 = '1' and soon....

you have (worst case) 8 bombs.. so you can plus char
thanx

mattapayne
New poster
Posts: 8
Joined: Thu Jun 17, 2004 5:50 am
Thanks,

Got it accepted.

Matt

dbwie
New poster
Posts: 6
Joined: Sun Jul 11, 2004 9:42 pm

### 10189 Minesweeper - help wanted (WA)

Hi, ANy help on the code below gratefully received ... NB This is not a college assignment - merely a hobbyist having ago. The code provides the right answers when I 'throw stuff at it', but I keep getting wa from both programming-challenges on oonline-judge.

Here's the code:

<code>
/*
@JUDGE_ID: 47559CM 10189 C++ ""
*/

#include <iostream>
using namespace std;

/* constants */
const char BOMB = '*';
const char BLANK = '.';

/* typedefs */
typedef struct {
int N;
int M;
char grid[10][10];
} field;

/* prototypes */
void showBoard(field, int);

//===================================================================
int main(void) {
int i,j, p, q; // loop counters
int fieldCount = 0; // number of 'fields' entered
field boards[5];
int N, M; // N = rows down,M = columns down
// get the dimensions
cin >> N >> M;
while (N!=0 && M!=0) {
boards[fieldCount].N=N;
boards[fieldCount].M=M;
// enter the board
for (i=0;i<N;i++) {
for (j=0;j<M;j++) {
cin >> boards[fieldCount].grid[j];
if (boards[fieldCount].grid[j] == BLANK) {
boards[fieldCount].grid[j] = '0';
}
}
}
// parse the board and generate the hints
for (i=0;i<N;i++) {
for (j=0;j<M;j++) {
if (boards[fieldCount].grid[j] == BOMB) {
// traverse the surrounding squares and update
for (p=i-1; p<=i+1; p++) {
for (q=j-1; q<=j+1; q++) {
if (boards[fieldCount].grid[p][q] != BOMB) {
// increment the number of hints
if ((p>=0) && (p<=N) && (q>=0) && (q<=M)) {
boards[fieldCount].grid[p][q]++;
}
}
}
}
}
}
};
//showBoard(board,N,M, fieldCount);
cin >> N >> M;
fieldCount++;
}

// print out the fields
for (p=0;p<fieldCount;p++) {
showBoard(boards[p],p);
}
return 0;
}
//===================================================================

void showBoard(field b, int fc) {
// display grid of n x m to stdout
int i,j; // loop coounters
cout << endl << "Field #" << fc+1 << ": " << endl;
for (i=0;i<b.N;i++) {
for (j=0;j<b.M;j++) {
cout << b.grid[j];
if ((j+1) % b.M == 0) {
cout << endl;
}
}
}
//cout << endl;
}

</code>[/code]

dbwie
New poster
Posts: 6
Joined: Sun Jul 11, 2004 9:42 pm

### Wa becomes a RE ....? (10189)

Now it's giving me a runtime error - I increased the array by a factor iof 10. I changed it back again and an further runtime error - now with the saem code as before but was returned with a WA .... Ummm.... now very confused!

dbwie
New poster
Posts: 6
Joined: Sun Jul 11, 2004 9:42 pm

### 10189 - WA

Hi, the following gives me WA on programming-challenges and RE on online-judge! Any ideas? I've read all teh previous posts and tested input with their suggestions and my code works here. Is there something special for the I/O? e.g. a blank line I'm missing??

Thanks in advance

Dave

Code: Select all

``````/*
@JUDGE_ID:  47559CM 10189 C++ ""
*/

#include <iostream>
using namespace std;

/* constants */
const char BOMB = '*';
const char BLANK = '.';

/* typedefs */
typedef struct {
int N;
int M;
char grid[10][10];
} field;

/* prototypes */
void showBoard(field, int);

//===================================================================
int main(void) {
int i,j, p, q;				// loop counters
int fieldCount = 0; 		// number of 'fields' entered
field boards[5];
int N, M;				// N = rows down,M = columns down
// get the dimensions
cin >> N >> M;
while (N!=0 && M!=0) {
boards[fieldCount].N=N;
boards[fieldCount].M=M;
// enter the board
for (i=0;i<N;i++) {
for (j=0;j<M;j++) {
cin >> boards[fieldCount].grid[i][j];
if (boards[fieldCount].grid[i][j] == BLANK) {
boards[fieldCount].grid[i][j] = '0';
}
}
}
// parse the board and generate the hints
for (i=0;i<N;i++) {
for (j=0;j<M;j++) {
if (boards[fieldCount].grid[i][j] == BOMB) {
// traverse the surrounding squares and update
for (p=i-1; p<=i+1; p++) {
for (q=j-1; q<=j+1; q++) {
if (boards[fieldCount].grid[p][q] != BOMB) {
// increment the number of hints
if ((p>=0) && (p<=N) && (q>=0) && (q<=M)) {
boards[fieldCount].grid[p][q]++;
}
}
}
}
}
}
};
//showBoard(board,N,M, fieldCount);
cin >> N >> M;
fieldCount++;
}

// print out the fields
for (p=0;p<fieldCount;p++) {
showBoard(boards[p],p);
}
return 0;
}
//===================================================================

void showBoard(field b, int fc) {
// display grid of n x m to stdout
int i,j;				// loop coounters
cout << endl << "Field #" << fc+1 << ": " << endl;
for (i=0;i<b.N;i++) {
for (j=0;j<b.M;j++) {
cout << b.grid[i][j];
if ((j+1) % b.M == 0) {
cout << endl;
}
}
}
//cout << endl;
}
``````

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### what the ..

This is a part of your code :
[c]
typedef struct {
int N;
int M;
char grid[10][10];
} field;
[/c]

And here is a line from the problem statement :
The first line of each field contains two integers n and m (0 < n,m <= 100) which stands for the number of lines and columns of the field respectively.
So why did you declare the grid size 10X10?

And you don't have to store the answer in an array and print it together at the end... better way is to print it immediately after each is generated.

Here is a slight modification of your code.

[c]

/*
@JUDGE_ID: 47559CM 10189 C++ ""
*/

#include <iostream>
using namespace std;

/* constants */
const char BOMB = '*';
const char BLANK = '.';

/* typedefs */
typedef struct {
int N;
int M;
char grid[105][105];
} field;

/* prototypes */
void showBoard(field, int);

//===================================================================
int main(void) {

int i,j, fc = 0, q; // loop counters
int p;
int fieldCount = 0; // number of 'fields' entered
field boards;
int N, M; // N = rows down,M = columns down
// get the dimensions
cin >> N >> M;
while (N!=0 && M!=0) {
boards.N=N;
boards.M=M;
// enter the board
for (i=0;i<N;i++) {
for (j=0;j<M;j++) {
cin >> boards.grid[j];
if (boards.grid[j] == BLANK) {
boards.grid[j] = '0';
}
}
}
// parse the board and generate the hints
for (i=0;i<N;i++) {
for (j=0;j<M;j++) {
if (boards.grid[j] == BOMB) {
// traverse the surrounding squares and update
for (p=i-1; p<=i+1; p++) {
for (q=j-1; q<=j+1; q++) {
if (boards.grid[p][q] != BOMB) {
// increment the number of hints
if ((p>=0) && (p<=N) && (q>=0) && (q<=M)) {
boards.grid[p][q]++;
}
}
}
}
}
}
};

//showBoard(board,N,M, fieldCount);
showBoard(boards, fc++);
cin >> N >> M;
fieldCount++;
}

// print out the fields

return 0;
}
//===================================================================

void showBoard(field b, int fc) {
// display grid of n x m to stdout
int i,j; // loop coounters
cout << endl << "Field #" << fc+1 << ": " << endl;
for (i=0;i<b.N;i++) {
for (j=0;j<b.M;j++) {
cout << b.grid[j];
if ((j+1) % b.M == 0) {
cout << endl;
}
}
}
//cout << endl;
}
[/c]

Note that the grid size is 105*105 and the board object is one dimensional and the output is printed as soon as it is generated.

And btw : Don't Show your id with the suffix on this forum ...
.. there might be some lunatics lurking around.

Hope it helps.

dbwie
New poster
Posts: 6
Joined: Sun Jul 11, 2004 9:42 pm

### Thanks

Thanks for your help with this - I had tried several sizes of the array but only up to 100 ea (except (doh!) that only gives 99 .... of crs). I had also tried printing out the answer each time, when that got WA I thought perhaps the output should be stored, then printed. I think the challenge wording and illustration is ambiguous in that regard

I shall recode with your suggestions.

Thanks again for your attention

dbwie
New poster
Posts: 6
Joined: Sun Jul 11, 2004 9:42 pm

### Thanks

Thanks for your help with this - I had tried several sizes of the array but only up to 100 ea (except (doh!) that only gives 99 .... of crs). I had also tried printing out the answer each time, when that got WA I thought perhaps the output should be stored, then printed. I think the challenge wording and illustration is ambiguous in that regard

I shall recode with your suggestions.

Thanks again for your attention

dbwie
New poster
Posts: 6
Joined: Sun Jul 11, 2004 9:42 pm

### Accepted

Thanks - Sohel for your help .... but not accepted on the programming-challenges website .......

nerocrux
New poster
Posts: 7
Joined: Fri Jul 30, 2004 5:14 am
Location: city of god

### 10189 -- WA

[cpp]#include <iostream>
using namespace std;

int main()
{
int n,m,i,j,count=1,flag=0;
char a[101][101];
int b[101][101]={0};
while(cin>>n>>m)
{
if(n==0&&m==0) break;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cin>>a[j];
}
for(i=1;i<n-1;i++)
for(j=1;j<m-1;j++)
{
if(a[j]=='*') b[j]=9;
else if(a[j]=='.')
{
if(a[i+1][j+1]=='*') b[j]++;
if(a[i+1][j]=='*') b[j]++;
if(a[i+1][j-1]=='*') b[j]++;
if(a[j+1]=='*') b[j]++;
if(a[j-1]=='*') b[i][j]++;
if(a[i-1][j+1]=='*') b[i][j]++;
if(a[i-1][j]=='*') b[i][j]++;
if(a[i-1][j-1]=='*') b[i][j]++;
}
}
for(j=1;j<m-1;j++)
{
if(a[0][j]=='*') b[0][j]=9;
else if(a[0][j]=='.')
{
if(a[0][j-1]=='*') b[0][j]++;
if(a[0][j+1]=='*') b[0][j]++;
if(a[1][j-1]=='*') b[0][j]++;
if(a[1][j]=='*') b[0][j]++;
if(a[1][j+1]=='*') b[0][j]++;
}
}
if(n>1) for(j=1;j<m-1;j++)
{
if(a[n-1][j]=='*') b[n-1][j]=9;
else if(a[n-1][j]=='.')
{
if(a[n-1][j-1]=='*') b[n-1][j]++;
if(a[n-1][j+1]=='*') b[n-1][j]++;
if(a[n-2][j-1]=='*') b[n-1][j]++;
if(a[n-2][j]=='*') b[n-1][j]++;
if(a[n-2][j+1]=='*') b[n-1][j]++;
}
}
for(i=1;i<n-1;i++)
{
if(a[i][0]=='*') b[i][0]=9;
else if(a[i][0]=='.')
{
if(a[i-1][0]=='*') b[i][0]++;
if(a[i+1][0]=='*') b[i][0]++;
if(a[i-1][1]=='*') b[i][0]++;
if(a[i][1]=='*') b[i][0]++;
if(a[i+1][1]=='*') b[i][0]++;
}
}
if(m>1) for(i=1;i<n-1;i++)
{
if(a[i][m-1]=='*') b[i][m-1]=9;
else if(a[i][m-1]=='.')
{
if(a[i-1][m-1]=='*') b[i][m-1]++;
if(a[i+1][m-1]=='*') b[i][m-1]++;
if(a[i-1][m-2]=='*') b[i][m-1]++;
if(a[i][m-2]=='*') b[i][m-1]++;
if(a[i+1][m-2]=='*') b[i][m-1]++;
}
}
if(a[0][0]=='*') b[0][0]=9;
else if(a[0][0]=='.')
{
if(a[0][1]=='*') b[0][0]++;
if(a[1][1]=='*') b[0][0]++;
if(a[1][0]=='*') b[0][0]++;
}
if(n>1)
{
if(a[n-1][0]=='*') b[n-1][0]=9;
else if(a[n-1][0]=='.')
{
if(a[n-2][0]=='*') b[n-1][0]++;
if(a[n-2][1]=='*') b[n-1][0]++;
if(a[n-1][1]=='*') b[n-1][0]++;
}
}
if(a[0][m-1]=='*') b[0][m-1]=9;
else if(a[0][m-1]=='.')
{
if(a[0][m-2]=='*') b[0][m-1]++;
if(a[1][m-2]=='*') b[0][m-1]++;
if(a[1][m-1]=='*') b[0][m-1]++;
}
if(m>1)
{
if(a[n-1][m-1]=='*') b[n-1][m-1]=9;
else if(a[n-1][m-1]=='.')
{
if(a[n-2][m-1]=='*') b[n-1][m-1]++;
if(a[n-2][m-2]=='*') b[n-1][m-1]++;
if(a[n-1][m-2]=='*') b[n-1][m-1]++;
}
}
if(flag==1) cout<<endl;
cout<<"Field #"<<count++<<":"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(b[i][j]==9) cout<<"*";
else cout<<b[i][j];
}
cout<<endl;
}
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
a[i][j]='.';
b[i][j]=0;
}
flag=1;
}
return 0;
}[/cpp]

here is my code..i dont know where goes wrong but i always got wa..
great thanks for help...

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
Hi nerocrux, i see your code but gives all the same anwers of my AC code , i give some tips that i hope that helps, look in my code i handle the '\n' or the '\0' in your code i dont find, this makes some errors, try to make the array to 105 and flush the 2 array before read new input
Hope its Helps
Keep posting !!

P.S.: I/O tricks in this problems =( sorry this is a straight forward problem.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
your code has many special cases and is kind of ugly to read. consider wrapping your minesweeper map by a frame of .'s to avoid all special cases

e.g. if u have a 3x3 minesweeper board, but a 5x5 frame around it

Code: Select all

``````.....
.   .
.   .
.   .
.....
``````
my code is 30 lines by doing this, and it makes things much easier to debug.

rs6
New poster
Posts: 2
Joined: Sun Sep 26, 2004 1:05 am
Location: Guanajuato

### 10189 Wrong Answer

Hi! I'm new here... i'm from Mexico and im 16 years old...

I have a problem with Minesweeper, i dont know... maybe the error
is on the output format, but i cant find it.... I have two diferent codes... on the first one i send the output inmediatly after one input and on the another code i send it after read all inputs

This is the one:
[cpp]
#include <stdio.h>

void imprime(int resultante[110][110], int n, int m, int count)
{

int i,j;

printf("Field #%d:\n", count);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
if(resultante[j]<9)
printf("%d", resultante[j]);

else
printf("*");

printf("\n");
}
printf("\n");
}

void leeDatos()
{

int count=1;
int n, m,i,j;
char map;
int resultante[110][110];

while(scanf("%d %d", &n, &m)!=EOF && (n!=0 && m!=0) )
{

for(i=0;i<n;i++)
for(j=0;j<m;j++)
resultante[j]=0;

scanf("\n");

for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%c", &map);
if(map=='*')
{
resultante[j]=9;

if(i-1>=0)
{
if(j-1>=0)
resultante[i-1][j-1]++;

if(j+1<m)
resultante[i-1][j+1]++;

resultante[i-1][j]++;

}
if(j-1>=0)
resultante[j-1]++;

if(j+1<m)
resultante[j+1]++;

if(i+1<n)
{
if(j-1>=0)
resultante[i+1][j-1]++;

if(j+1<m)
resultante[i+1][j+1]++;

resultante[i+1][j]++;
}

}

}
if(i<m-1)
scanf("\n");

}

imprime(resultante,m,n,count);
count++;

}

delete[] resultante;

}

int main()
{
leeDatos();

return 0;

}
[/cpp]

This is the second one:
[cpp]

#include <stdio.h>

struct sNodo
{

int n;
int m;
int **resultante;

sNodo *siguiente;
};

sNodo *inicio;

void imprime()
{

sNodo *tmp;
int i,j;
long long int count=1;

for(tmp=inicio;tmp!=NULL;tmp=tmp->siguiente)
{

printf("Field #%ld:\n", count);
for(i=0;i<tmp->n;i++)
{
for(j=0;j<tmp->m;j++)
if(tmp->resultante[j]<9)
printf("%d", tmp->resultante[j]);

else
printf("*");

printf("\n");
}

printf("\n");

count++;

delete[] tmp->resultante;

}
}

void leeDatos()
{

int n, m,i,j;
char map;
sNodo *tmp1, *tmp2;

while(scanf("%d %d", &n, &m)!=EOF && (n!=0 && m!=0) )
{

tmp1=new sNodo;

if(inicio==NULL)
inicio=tmp1;

else
tmp2->siguiente=tmp1;

tmp1->n=n;
tmp1->m=m;

tmp1->resultante=new int*[n];
for(i=0;i<n;i++)
tmp1->resultante=new int[m];

for(i=0;i<n;i++)
for(j=0;j<m;j++)
tmp1->resultante[j]=0;

scanf("\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%c", &map);
if(map=='*')
{
tmp1->resultante[i][j]=9;

if(i-1>=0)
{
if(j-1>=0)
tmp1->resultante[i-1][j-1]++;

if(j+1<tmp1->m)
tmp1->resultante[i-1][j+1]++;

tmp1->resultante[i-1][j]++;

}
if(j-1>=0)
tmp1->resultante[i][j-1]++;

if(j+1<tmp1->m)
tmp1->resultante[i][j+1]++;

if(i+1<tmp1->n)
{
if(j-1>=0)
tmp1->resultante[i+1][j-1]++;

if(j+1<tmp1->m)
tmp1->resultante[i+1][j+1]++;

tmp1->resultante[i+1][j]++;
}

}

}
if(i<m-1)
scanf("\n");
}

tmp1->siguiente=NULL;
tmp2=tmp1;

}

}

int main (void)
{

leeDatos();
imprime();

return 0;
}

[/cpp]

But both WA..... i hope that you'll help me
Thnx.

Joe
"La vida es sue