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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10189 - Minesweeper

Post by brianfry713 » Mon Aug 27, 2012 8:49 pm

Use a 2d matrix.
Check input and AC output for thousands of problems on uDebug!

KungFuLambChops
New poster
Posts: 2
Joined: Wed Sep 05, 2012 4:56 am

10189 Minesweeper

Post by KungFuLambChops » Wed Sep 05, 2012 6:47 am

I'm pounding my head in frustration. This seems like an easy problem and, in fact, the solution I'm posting in this message passed the test on CodeChef. But when I try to submit it here, I get a runtime error. The code compiles on my own machine, though, and passes the tests I throw at it. I will send a handwritten postcard from California, expressing my gratitude to whomever can point me to the source of this bug. Okay, it's not much of an incentive, but it's the best I can do. Thank you very much in advance to whomever can help.

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define LINE_MAX 102

int main(int argc, const char *argv[])
{
    int c=0, cols=0, lines=0;

    while(1) {
        char *line = malloc(sizeof(char)*cols);

        /* increment curr field being processed */
        c++;

        fgets(line, LINE_MAX, stdin);
        sscanf(line, "%d %d", &lines, &cols);

        /* end program if indicated */
        if(lines==0 && cols==0) break;

        /* print line after fieldset if program continues */
        if(c>1) printf("\n");

        int **grid, g_i, g_j, i, j;

        /* initialize grid */
        grid = malloc(sizeof(int **)*lines);
        for(i=0; i<lines; i++) {
            grid[i] = malloc(sizeof(int *)*cols);
            for(j=0; j<cols; j++) grid[i][j]=0;
        }

        /* grab lines and tally grid */
        for(i=0; i<lines; i++) {
            fgets(line, LINE_MAX, stdin);

            for(j=0; j<cols; j++) {

                if(line[j]=='*') {
                    for(g_i=-1; g_i<2; g_i++) {
                        for(g_j=-1; g_j<2; g_j++) {
                            if( i+g_i<0 
                                || i+g_i>lines-1 
                                || j+g_j<0 
                                || j+g_j>cols-1 ) 
                                continue;

                            if(g_i==0 && g_j==0)
                                grid[i+g_i][j+g_j] = -1;
                            else if(grid[i+g_i][j+g_j] != -1)
                                grid[i+g_i][j+g_j]++;
                        }
                    }
                }
            }
        }

        /* print out result */
        printf("Field #%d:\n", c);
        for(i=0; i<lines; ++i) {
            for(j=0; j<cols; ++j) {
                if(grid[i][j]==-1)
                    printf("*");
                else
                    printf("%d", grid[i][j]);
            }
            printf("\n");
        }

        /* free allocated memory */
        free(line);
        for(i=0; i<lines; i++) free(grid[i]);
        free(grid);
    }

    return 0;
}

KungFuLambChops
New poster
Posts: 2
Joined: Wed Sep 05, 2012 4:56 am

Re: 10189 Minesweeper

Post by KungFuLambChops » Wed Sep 05, 2012 9:27 am

Issue resolved. Thanks to those of you who at least took a look at the code.

The posted code was leaking memory and doing invalid reads. I needed to fix two things.

1) I needed to change this,

Code: Select all

        char *line = malloc(sizeof(char)*cols);
to this,

Code: Select all

        char *line = malloc(sizeof(char)*LINE_MAX);
because two lines of code later I was doing this,

Code: Select all

        fgets(line, LINE_MAX, stdin);
and so the first version of the line wasn't allocating enough memory.

2) I needed to free the line variable when the time came to stop the program, so I changed this,

Code: Select all

        /* end program if indicated */
        if(lines==0 && cols==0)
            break;
to this,

Code: Select all

        /* end program if indicated */
        if(lines==0 && cols==0) {
            free(line);
            break;
        }
and when I ran valgrind all the errors were resolved. Solution ACcepted, life is grand.

Bob
New poster
Posts: 3
Joined: Fri Sep 14, 2012 3:15 pm

10189 Minesweeper - WA

Post by Bob » Fri Sep 14, 2012 3:20 pm

Hi there, thanks for taking the time to read. In exchange for the favor I'll try to keep this short.
I've been strolling the forums for help but couldn't find anything to fix my problem.

I have
  • Tried all boundary values for exceptions.
  • Added newline characters in between fields but NOT after the last field.
In addition, I've tried to uva simulator but it wouldn't accept any of my files (even the ones that had AC).

My code:

Code: Select all

import java.util.*;

/**
 * 
 * problem 10189
 * 
 */
public class Main{
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		
		int count = 0;
		
		while(input.hasNextInt()) {
			int m = input.nextInt();
			int n = input.nextInt();
			
			if ((m == 0) && (n == 0))
				break;
			
			if (count != 0)
				System.out.print('\n');
			
			count++;
			
			boolean[][] matrix = new boolean[m][n];
			char[][] result = new char[m][n];
			
			for (int i = 0; i < m; i++) {
				String current = input.next("[\\*\\.]*");
				
				for (int j = 0; j < n; j++)
					matrix[i][j] = (current.charAt(j) == '*') ? true : false;	
			}
			
			for (int i = 0; i < m; i++) {	
				for (int j = 0; j < n; j++) {
					if (matrix[i][j])
							result[i][j] = '*';
					else {
						int mines = 0;
						
						// Horizontally
						if (i > 0)				// Left
							if (matrix[i-1][j])
								mines++;
						
						if (i < m - 1)			// Right
							if (matrix[i+1][j])
								mines++;
						
						// Vertically
						if (j > 0)				// Top
							if (matrix[i][j-1])	
								mines++;
							
						if (j < n -1)			// Bottom
							if (matrix[i][j+1])
								mines++;
						
						// Diagonally			// Top Left
						if ((i > 0) && (j > 0))
							if (matrix[i-1][j-1])
								mines++;
						
						if ((i < m - 1) && (j > 0))	// Bottom Left
							if (matrix[i+1][j-1])
								mines++;
						
						if ((i > 0) && (j < n - 1))	// Top Right
							if (matrix[i-1][j+1])
								mines++;
						
						if ((i < m - 1) && (j < n - 1))	// Bottom Left
							if (matrix[i+1][j+1])
								mines++;
						
						result[i][j] = ("" + mines).charAt(0);
					}
				}
			}
			
			System.out.println("Field #" + count + ":");
			
			for (int i = 0; i < m; i++) {	
				for (int j = 0; j < n; j++) {
					System.out.print(result[i][j]);
				}
				System.out.print('\n');
			}
		}
		input.close();
	}
}

Any help would greatly be appreciated.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10189 Minesweeper - WA

Post by brianfry713 » Fri Sep 14, 2012 9:12 pm

That is AC code.
Check input and AC output for thousands of problems on uDebug!

Bob
New poster
Posts: 3
Joined: Fri Sep 14, 2012 3:15 pm

Re: 10189 Minesweeper - WA

Post by Bob » Fri Sep 14, 2012 9:20 pm

... No idea how this happened, but after submitting for a 4th time it did, indeed, get miraculously accepted.

Thank you very much.

MewCatcher
New poster
Posts: 19
Joined: Tue Oct 30, 2012 8:19 am

10189 Puzzle WA...I cannot find out the reason

Post by MewCatcher » Tue Oct 30, 2012 8:26 am

I know it's not a good code at all, but I just want to know the very reason... :o
Thanks everyone opening this page!~ :)
Hope the kind you can help me!~ :D

Code: Select all

#include <stdio.h>
#include <string.h>

/*Sample Input
4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0

Sample Output
Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100

*/

int main( )
{
    int n, m, i, j, Counter = 1;
    bool Flag1, Flag2, Flag3, Flag4;
    char F[ 100 ][ 100 ];
    short D[ 100 ][ 100 ];
    while( scanf( "%d%d", &n, &m ), n ) {
        for( i = 0; i < n; i ++ ) scanf( "%s", F[ i ] );
        if( Counter != 1 ) printf( "\n" );
        
        printf( "Field #%d:\n", Counter );
        memset( D, 0, sizeof( D ) );
        for( i = 0; i < n; i ++ ) {//x
            for( j = 0; j < m; j ++ ) {//y
                if( F[ i ][ j ] == '*' ) {
                    printf( "%c", '*' );
                    continue;
                }
                
                if( i - 1 >= 0 ) Flag1 = true;//x-1
                if( i + 1 < n ) Flag2 = true;//x+1
                if( j - 1 >= 0 ) Flag3 = true;//y-1
                if( j + 1 < m ) Flag4 = true;//y+1
                
                if( Flag1 && Flag3 ) if( F[ i - 1 ][ j - 1 ] == '*' ) D[ i ][ j ] ++;
                if( Flag3 ) if( F[ i ][ j - 1 ] == '*' ) D[ i ][ j ] ++;
                if( Flag2 && Flag3 ) if( F[ i + 1 ][ j - 1 ] == '*' ) D[ i ][ j ] ++;
                if( Flag1 ) if( F[ i - 1 ][ j ] == '*' ) D[ i ][ j ] ++;
                if( Flag2 ) if( F[ i + 1 ][ j ] == '*' ) D[ i ][ j ] ++;
                if( Flag1 && Flag4 ) if( F[ i - 1 ][ j + 1 ] == '*' ) D[ i ][ j ] ++;
                if( Flag4 ) if( F[ i ][ j + 1 ] == '*' ) D[ i ][ j ] ++;
                if( Flag2 && Flag4 ) if( F[ i + 1 ][ j + 1 ] == '*' ) D[ i ][ j ] ++;
                printf( "%hd", D[ i ][ j ] );
                
                Flag1 = false;
                Flag2 = false;
                Flag3 = false;
                Flag4 = false;
            }
            printf( "\n" );
        }
        Counter ++;
    }
    return 0;
}


MewCatcher
New poster
Posts: 19
Joined: Tue Oct 30, 2012 8:19 am

Re: 10189 Puzzle WA...I cannot find out the reason

Post by MewCatcher » Tue Oct 30, 2012 1:45 pm

Please, help me - a newbie.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10189 Puzzle WA...I cannot find out the reason

Post by brianfry713 » Wed Oct 31, 2012 1:09 am

That is AC code. You should include space for the trailing null char.
char F[ 100 ][ 101 ];
Check input and AC output for thousands of problems on uDebug!

MewCatcher
New poster
Posts: 19
Joined: Tue Oct 30, 2012 8:19 am

Re: 10189 Puzzle WA...I cannot find out the reason

Post by MewCatcher » Wed Oct 31, 2012 8:47 am

Thank you very very much with my most appreciate!!!

iamtechaddict
New poster
Posts: 1
Joined: Thu Nov 15, 2012 2:26 pm

Re: 10189 - Minesweeper

Post by iamtechaddict » Thu Nov 15, 2012 2:34 pm

Getting WA

Code: Select all

#include<iostream>
#include<cstdio>
#include <vector>
#include <string>
using namespace std;
int main(){
    int n,m,cas=1;
    while(cin>>n>>m){
        if(n==0&&m==0)break;
        vector<string> s;
        string x;
        for(int i=0;i<n;i++){
            cin>>x;
            s.push_back(x);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(s[i][j]!='*'){
                    s[i][j]=(i+1<n&&s[i+1][j]=='*')+(j+1<m&&s[i][j+1]=='*')+(i+1<n&&j+1<m&&s[i+1][j+1]=='*')+(i>0&&s[i-1][j]=='*')+(j>0&&s[i][j-1]=='*')+(i>0&&j>0&&s[i-1][j-1]=='*')+(i+1<n&&j>0&&s[i+1][j-1]=='*')+(i>0&&j+1<m&&s[i-1][j+1]=='*')+'0';
                }
            }
        }
        cout<<"Field #"<<cas<<":\n";
        cas++;
        for(int i=0;i<n;i++){
            cout<<s[i]<<endl;
        }
    }
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10189 - Minesweeper

Post by brianfry713 » Thu Nov 15, 2012 11:53 pm

There must be an empty line between field outputs.
Check input and AC output for thousands of problems on uDebug!

bimajw
New poster
Posts: 6
Joined: Wed Nov 14, 2012 5:26 am

Re: 10189 - Minesweeper

Post by bimajw » Thu Nov 22, 2012 4:52 am

RE please help me..
this my code
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
int i,j,n,m,k;
for(k=1;;k++){
char array[100][100];
scanf("%d%d",&n,&m);
if(n==0&&m==0){break;}
if(n>0&&n<=100&&m>0&&m<=100){
array[n][m];
for(i=0;i<n;i++){
for(j=0;j<m;j++){
scanf("%c",&array[j]);
if(array[j]=='\n'){
free(&array[j]);
j--;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(array[j]=='.'){
array[j]='0';
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(array[j]=='*'){
if(array[i-1][j-1]!='*'){array[i-1][j-1]+=1;}
if(array[i-1][j]!='*'){array[i-1][j]+=1;}
if(array[i-1][j+1]!='*'){array[i-1][j+1]+=1;}
if(array[j-1]!='*'){array[j-1]+=1;}
if(array[j+1]!='*'){array[j+1]+=1;}
if(array[i+1][j-1]!='*'){array[i+1][j-1]+=1;}
if(array[i+1][j]!='*'){array[i+1][j]+=1;}
if(array[i+1][j+1]!='*'){array[i+1][j+1]+=1;}
}
}
}
printf("Field #%d:\n",k);
for(i=0;i<n;i++){
for(j=0;j<m;j++){
printf("%c",array[i][j]);
}printf("\n");
}
}
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10189 - Minesweeper

Post by brianfry713 » Fri Nov 30, 2012 7:33 am

Your RE on the sample input is an invalid pointer during the call to free().
Also There must be an empty line between field outputs.
Check input and AC output for thousands of problems on uDebug!

mahbub2012
New poster
Posts: 5
Joined: Fri Nov 09, 2012 11:33 pm

Re: 10189 - Minesweeper

Post by mahbub2012 » Mon Dec 10, 2012 11:36 pm

Got Accepted. :D :D

Code: Select all

removed

Post Reply

Return to “Volume 101 (10100-10199)”