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:

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
thanx

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

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
New poster
Posts: 12
Joined: Sat Mar 13, 2004 6:15 pm
Location: Sampa - Brazil
Contact:

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
thanx

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

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

Thanks,

Got it accepted.

Matt

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

10189 Minesweeper - help wanted (WA)

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
New poster
Posts: 6
Joined: Sun Jul 11, 2004 9:42 pm

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

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
New poster
Posts: 6
Joined: Sun Jul 11, 2004 9:42 pm

10189 - WA

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;
 }

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

what the ..

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. :oops:

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. :roll:

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

Hope it helps. 8)

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

Thanks

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
New poster
Posts: 6
Joined: Sun Jul 11, 2004 9:42 pm

Thanks

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
New poster
Posts: 6
Joined: Sun Jul 11, 2004 9:42 pm

Accepted

Post by dbwie » Sun Jul 18, 2004 1:28 am

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

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...

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

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
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

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
New poster
Posts: 2
Joined: Sun Sep 26, 2004 1:05 am
Location: Guanajuato

10189 Wrong Answer

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
"La vida es sue

Post Reply

Return to “Volume 101 (10100-10199)”