10189 - Minesweeper

grirus · Post by **grirus** » Thu Jun 17, 2004 8:04 pm

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

mattapayne · Post by **mattapayne** » Thu Jun 17, 2004 10:05 pm

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 · Post by **grirus** » Fri Jun 18, 2004 1:56 pm

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

mattapayne · Post by **mattapayne** » Fri Jun 18, 2004 8:52 pm

Thanks,

Got it accepted.

Matt

dbwie · Post by **dbwie** » Sun Jul 11, 2004 9:50 pm

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 · Post by **dbwie** » Sun Jul 11, 2004 9:57 pm

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 · Post by **dbwie** » Thu Jul 15, 2004 11:17 am

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 · Post by **sohel** » Thu Jul 15, 2004 1:58 pm

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 · Post by **dbwie** » Sun Jul 18, 2004 1:11 am

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 · Post by **dbwie** » Sun Jul 18, 2004 1:12 am

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 · Post by **dbwie** » Sun Jul 18, 2004 1:28 am

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

nerocrux · Post by **nerocrux** » Mon Aug 02, 2004 6:11 pm

[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 · Post by **Ghust_omega** » Sat Sep 04, 2004 12:03 pm

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 · Post by **Minilek** » Sat Sep 04, 2004 6:18 pm

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 · Post by **rs6** » Sun Sep 26, 2004 4:00 am

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

OJ Board

10189 - Minesweeper

10189 Minesweeper - help wanted (WA)

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

10189 - WA

what the ..

Thanks

Thanks

Accepted

10189 -- WA

10189 Wrong Answer