10189 - Minesweeper

[brianfry713]

Use a 2d matrix.

[KungFuLambChops]

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]

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]

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]

That is AC code.

[Bob]

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

Thank you very much.

[MewCatcher]

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

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]

Please, help me - a newbie.

[brianfry713]

That is AC code. You should include space for the trailing null char.
char F[ 100 ][ 101 ];

[MewCatcher]

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

[iamtechaddict]

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]

There must be an empty line between field outputs.

[bimajw]

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]

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.

[mahbub2012]

Got Accepted.

Code: Select all

removed