10189 - Minesweeper

[jdmetz]

Why don't you worry about the boundaries? Won't your code fail on the second of these two cases:

Code: Select all

4 4
****
****
****
****

3 3
...
...
...

[Fuad Hassan_IIUC(DC)]

i have changed the code a bit but still getting WA. here is mu chaged code.

#include<stdio.h>
#include<iostream.h>
int main()
{
char str[105][105];
int i,j,count,a,b,field=1;
while(cin>>a>>b)
{
if(a==0&&b==0)
break;
for(i=0;i<a;i++)
{
for(j=0;j<b;j++)
{
cin>>str[j];

}
}
printf("Field #%d:\n",field);
for(i=0;i<a;i++)
{

for(j=0;j<b;j++)
{
count=0;
if(str[j]=='*')
cout<<"*";
else
{

if(str[i-1][j-1]=='*')
count++;
if(str[i-1][j]=='*')
count++;
if(str[i-1][j+1]=='*')
count++;
if(str[j-1]=='*')
count++;
if(str[j+1]=='*')
count++;
if(str[i+1][j-1]=='*')
count++;
if(str[i+1][j]=='*')
count++;
if(str[i+1][j+1]=='*')
count++;
printf("%d",count);
}
}
printf("\n");
}
field++;
cout<<endl;
}
return 0;
}

[sohel]

you are still not checking the boundary case..

when using i+1 or i - 1 or j+1 or j-1, make sure that coordiante lies within the grid, otherwise you get to consider points outside the grid and that may lead to error.

[Roby]

Please help me to solve this annoying message (-->PE), why can't I perfectly solve this problem?

Below is my code:

Code: Select all

#include <stdio.h>
#include <string.h>
#define MAX 105
#define SIZE 100

char map[SIZE][MAX];
int flag[SIZE][MAX];

void initMap( void )
{
 int i = 0;

 for ( i = 0; i < SIZE; i++ )
    memset( map[i], '\0', sizeof( map[i] ) );
}

void initFlag( void )
{
 int i = 0, j = 0;

 for ( i = 0; i < SIZE; i++ )
    for ( j = 0; j < MAX; j++ )
       flag[i][j] = 0;
}

void countMine( const int m, const int n )
{
 int i = 0, j = 0;

 for ( i = 0; i < m; i++ )
    for ( j = 0; j < n; j++ )
       if ( map[i][j] == '*' )
       {
          flag[i][j] = 100;

          if ( map[i - 1][j] == '.' && i != 0 ) // Up
             flag[i - 1][j]++;

          if ( map[i - 1][j + 1] == '.' && i != 0 && j != n ) // Up-right
             flag[i - 1][j + 1]++;

          if ( map[i][j + 1] == '.' && j != n ) // Right
             flag[i][j + 1]++;

          if ( map[i + 1][j + 1] == '.' && i != m && j != n ) // Down-right
             flag[i + 1][j + 1]++;

          if ( map[i + 1][j] == '.' && i != m ) // Down
             flag[i + 1][j]++;

          if ( map[i + 1][j - 1] == '.' && i != m && j != 0 ) // Down-left
             flag[i + 1][j - 1]++;

          if ( map[i][j - 1] == '.' && j != 0 ) // Left
             flag[i][j - 1]++;

          if ( map[i - 1][j - 1] == '.' && i != 0 && j != 0 ) // Up-left
             flag[i - 1][j - 1]++;
       }
}

void printAnswer( const int m, const int n )
{
 int i = 0, j = 0;

 for ( i = 0; i < m; i++ )
 {
    for ( j = 0; j < n; j++ )
       if ( flag[i][j] == 100 )
          printf( "*" );
       else
          printf( "%d", flag[i][j] );

    printf( "\n" );
 }

 printf( "\n" );
}

int main()
{
 int m = 0, n = 0, test = 1;
 int i = 0;

 while ( scanf( "%d %d\n", &m, &n ) == 2 )
 {
    if ( m == 0 && n == 0 )
       break;

    initMap();
    initFlag();

    for ( i = 0; i < m; i++ )
       gets( map[i] );

    printf( "Field #%d:\n", test++ );

    countMine( m, n );
    printAnswer( m, n );
 }

 return 0;
}

Any idea.................................................

Before God, we are all equally wise and equally foolish

[Rocky]

Check out the problem statment

There must be an empty line between field outputs

So the empty line must print between two test case not after each test case your programm print empty line after each test case with the last
terminate case that is 0 0.
now i modiify your programme and got acc without pe. see it

Code: Select all

#include <stdio.h> 
#include <string.h> 
#define MAX 105 
#define SIZE 100 

char map[SIZE][MAX]; 
int flag[SIZE][MAX]; 

void initMap( void ) 
{ 
 int i = 0; 

 for ( i = 0; i < SIZE; i++ ) 
    memset( map[i], '\0', sizeof( map[i] ) ); 
} 

void initFlag( void ) 
{ 
 int i = 0, j = 0; 

 for ( i = 0; i < SIZE; i++ ) 
    for ( j = 0; j < MAX; j++ ) 
       flag[i][j] = 0; 
} 

void countMine( const int m, const int n ) 
{ 
 int i = 0, j = 0; 

 for ( i = 0; i < m; i++ ) 
    for ( j = 0; j < n; j++ ) 
       if ( map[i][j] == '*' ) 
       { 
          flag[i][j] = 100; 

          if ( map[i - 1][j] == '.' && i != 0 ) // Up 
             flag[i - 1][j]++; 

          if ( map[i - 1][j + 1] == '.' && i != 0 && j != n ) // Up-right 
             flag[i - 1][j + 1]++; 

          if ( map[i][j + 1] == '.' && j != n ) // Right 
             flag[i][j + 1]++; 

          if ( map[i + 1][j + 1] == '.' && i != m && j != n ) // Down-right 
             flag[i + 1][j + 1]++; 

          if ( map[i + 1][j] == '.' && i != m ) // Down 
             flag[i + 1][j]++; 

          if ( map[i + 1][j - 1] == '.' && i != m && j != 0 ) // Down-left 
             flag[i + 1][j - 1]++; 

          if ( map[i][j - 1] == '.' && j != 0 ) // Left 
             flag[i][j - 1]++; 

          if ( map[i - 1][j - 1] == '.' && i != 0 && j != 0 ) // Up-left 
             flag[i - 1][j - 1]++; 
       } 
} 

void printAnswer( const int m, const int n ) 
{ 
 int i = 0, j = 0; 

 for ( i = 0; i < m; i++ ) 
 { 
    for ( j = 0; j < n; j++ ) 
       if ( flag[i][j] == 100 ) 
          printf( "*" ); 
       else 
          printf( "%d", flag[i][j] ); 

    printf( "\n" ); 
 } 

} 

int main() 
{ 
 int m = 0, n = 0, test = 1; 
 int i = 0,end=0; 

 while ( scanf( "%d %d\n", &m, &n )) 
 { 
	if(m==0&&n==0)
		break;
	if(end)
		printf("\n");

    initMap(); 
    initFlag(); 

    for ( i = 0; i < m; i++ ) 
       gets( map[i] ); 

    printf( "Field #%d:\n", test++ ); 

    countMine( m, n ); 
    printAnswer( m, n ); 
	end = 1;
 } 

 return 0; 
}

GOOD LUCK
Rocky

[trance8]

Code: Select all

#include <iostream.h>

int main(int argc, char* argv[])
{
 int n,m,p1,p2,licz;
 char *tab,*tab2;

 while(1)
 {
  cin>>n>>m;
  if ((n==0) && (m==0)) break;
  if (licz) cout<<endl;
  tab = new char [n*m];
  tab2 = new char [n*m];
  for (p1=0;p1<n*m;++p1)
  {
   tab2[p1]='0';
  }
  for (p1=0;p1<n;++p1)
  {
   for (p2=0;p2<m;++p2)
   {
    cin>>tab[p1*m+p2];
   }
  } // for p1

  for (p1=0;p1<n;++p1)
  {
   for (p2=0;p2<m;++p2)
   {
    if (tab[p1*m+p2]=='*')
    {
     tab2[p1*m+p2]='*';

     if (p1>0)
     {
      if (p2>0)
      {
       if (tab2[(p1-1)*m+p2-1]!='*') tab2[(p1-1)*m+p2-1]++;
      }
      if (p2<m-1)
      {
       if (tab2[(p1-1)*m+p2+1]!='*') tab2[(p1-1)*m+p2+1]++;
      }

      if (tab2[(p1-1)*m+p2]!='*') tab2[(p1-1)*m+p2]++;
     } // if (p1>0)

     if (p1<n-1)
     {
      if (p2>0)
      {
       if (tab2[(p1+1)*m+p2-1]!='*') tab2[(p1+1)*m+p2-1]++;
      }
      if (p2<m-1)
      {
       if (tab2[(p1+1)*m+p2+1]!='*') tab2[(p1+1)*m+p2+1]++;
      }

      if (tab2[(p1+1)*m+p2]!='*') tab2[(p1+1)*m+p2]++;
     }

     if (p2>0)
     {
      if (tab2[p1*m+p2-1]!='*') tab2[p1*m+p2-1]++;
     }
     if (p2<m-1)
     {
      if (tab2[p1*m+p2+1]!='*') tab2[p1*m+p2+1]++;
     }
     if (tab2[p1*m+p2]!='*') tab2[p1*m+p2]++;

    }

   } // for p2
  } // for p1
  cout<<"Field #"<<++licz<<":"<<endl;
  for (p1=0;p1<n;++p1)
  {
   for (p2=0;p2<m;++p2)
   {
    cout<<tab2[p1*m+p2];;
   }
   cout<<endl;
  }

  delete [] tab;
  delete [] tab2;
 }
 return 0;
}

Why WA??

edit: licz=0 -> I forgot Now is OK.

[SP8472]

The code works on lots of test cases, including any "special" case I could think of. I believe also made the input parsing as robust as I possibly could. So...why does this code get WA? I compared it to code posted here that people said to be accepted, and I don't think I'm doing anything differently.

Code: Select all

/* DELETED */

[mamun]

My goodness! You forgot to initiate fld in main().

[SP8472]

Accepted.

Please excuse me while I go beat my head against the wall a few times. Hard.

I've been debugging this thing for ages, including two rewrites.

My local compiler just quietly initializes the variable to zero. It doesn't even warn, even though I'm using -Wall.

[mamun]

Take it easy. Don't break your head.
Why don't you better delete your code from the post?

[SP8472]

Just checked the gcc manpage. According to that, gcc is unable to warn about the use of uninitialized variables if not compiling with (at least) -O1. Guess I'll have to add that to my standard compilation parameters to avoid this kind of embarrassment in the future.

[Roby]

thanx Rocky
Sorry for the late reply...

[SigmaJargon]

I keep on getting WA for this, but I can't for the life of me see what is wrong.

Here is the source code and two test cases. If anybody could please explain where I am going wrong, it would be greatly appreciated.

Code: Select all

import java.io.*;

class Main
{

    int[][] SweeperField;
    
    void SetupSweeperField(int x, int y)
    {
        
        SweeperField = new int[x][y];
        
    }
    
    String Begin(String Input)
    {
        
        int Axis = Input.indexOf(" ");
        
        byte x = Byte.parseByte(Input.substring(0, Axis));
        byte y = Byte.parseByte(Input.substring(Axis + 1, Input.length()));
        
        SetupSweeperField(x,y);
        
        for (int i = 0; i < x; i++)
        {
            
            Input = readLn(255);
            int LatestMine = Input.indexOf("*");
            
            while (LatestMine != -1)
            {
                
                Increment(i, LatestMine);
                LatestMine = Input.indexOf("*", LatestMine+1);
                
            }
            
        }

        return ToString();
        
    }
    
    void Begin()
    {
        
        String Answer = "";
        
        String Input = readLn(255);
        
        int Counter = 1;
        
        while (!Input.equals("0 0"))
        {
            
            Answer += "Field #" + Counter + ":\n" + Begin(Input) + "\n";
            Input = readLn(255);
            Counter++;
            
        }
        
        System.out.print(Answer.substring(0, Answer.length() - 2));
        
    }
    
    static void main(String[] args)
    {
        
        Main Sweeper = new Main();
        Sweeper.Begin();
        
    }
    
    void Increment(int x, int y)
    {
        
        for (int i = -1; i <= 1; i++)
        {
            
            for (int j = -1; j <= 1; j++)
            {
                
                if ((((x+i) >= 0) && ((x+i) < SweeperField.length) && ((y+j) >= 0) && ((y+j) < SweeperField[0].length)))
                {
                    
                    SweeperField[x+i][y+j]++;
                    
                }
                
            }
        
        }
        
        SweeperField[x][y] = -5;
        
    }
        
    String ToString()
    {
        
        String Answer = "";
        
        for (int i = 0; i < SweeperField.length; i++)
        {
            
            for (int j = 0; j < SweeperField[0].length; j++)
            {
                
                if (SweeperField[i][j] < 0)
                    Answer += "*";
                else
                    Answer += SweeperField[i][j];
                
            }
            
            Answer += "\n";
            
        }
        
        return Answer;
        
    }

    static String readLn (int maxLg)
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = "";
     
        try
        {
            
            while (lg < maxLg)
            {
                
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
                
           }
           
        }
        catch (IOException e)
        {
            
            return (null);
        
        }
     
        if ((car < 0) && (lg == 0))
            return (null);
            
        return (new String (lin, 0, lg));
    }
    
}

Code: Select all

3 4
...*
**..
..*.
5 5
..*..
..*..
**...
.....
....*
3 6
***..*
......
..*...
0 0
Field #1:
222*
**32
23*1

Field #2:
02*20
24*20
**210
22111
0001*

Field #3:
***11*
243211
01*100

Code: Select all

2 2
..
.*
3 3
..*
**.
...
1 8
....**.*
10 7
.......
...*..*
*....**
......*
..*....
.......
.......
..*...*
*...*..
*.....*
0 0
Field #1:
11
1*

Field #2:
23*
**2
221

Field #3:
0001**2*

Field #4:
0011111
111*23*
*1112**
121113*
01*1011
0111000
0111011
12*212*
*312*32
*20112*

[Qodeus]

Hi!
I have just started programming in C++, and I found this easy problem. I have submited solutions for this problem a lot of times and always the answer from the judge is Runtime Error. And, also, it seams to me that for every test case I can think of the program works fine.
This is my code.

Code: Select all

#include <iostream>
#include <string>
using namespace std;
char mines[101][101];

int count(int red,int kol,int maxred, int maxkol)
{
    int u=0;
    if (red!=maxred)
    {
       if (mines[red+1][kol]=='*') u++;
    }
    if (red!=1)
    {
       if (mines[red-1][kol]=='*') u++;
    }
    if (kol!=maxkol)
    {
       if (mines[red][kol+1]=='*') u++;
    }
    if (kol!=1)
    {
       if (mines[red][kol-1]=='*') u++;
    }
    
    if (kol!=1&&red!=1)
    {
       if (mines[red-1][kol-1]=='*') u++;
    }
    
    if (kol!=maxkol&&red!=maxred)
    {
       if (mines[red+1][kol+1]=='*') u++;
    }
    
    if (kol!=1&&red!=maxred)
    {
       if (mines[red+1][kol-1]=='*') u++;
    }
    
    if (kol!=maxkol&&red!=1)
    {
       if (mines[red-1][kol+1]=='*') u++;
    }

    return u;
}


int main()
{
    int n=0,m=0,q=0;
    char nmines[101][101];

    string s[100],s1="";
    while(1)
    {


         cin >> n >> m;


       if (n==0||m==0) return 0;
       q++;
       
       for (int i=1;i<=n;i++)
       {
           do
           {
               cin >> s[i];
           }
           while (s[i].length()!=m);
       }
      
       for (int i=1;i<=n;i++)
       {
           for (int j=0;j<s[i].length();j++)
           {
               s1=s[i];
               mines[i][j+1]=s1[j];
           }   
       }
       cout << "Field #" << q << ":" << endl;
       for (int i=1;i<=n;i++)
       {
           for (int j=1;j<=m;j++)
           {
               if (mines[i][j]!='*') 
                  nmines[i][j]=count(i,j,n,m)+'0';
               else
                   nmines[i][j]='*';
           }
       }
       
       for (int i=1;i<=n;i++)
       {
           for (int j=1;j<=m;j++)
           {
               cout << nmines[i][j];
           }
           cout << endl;
       }
       cout << endl;
    }
    return 0;
}

Please could someone help me find out what the problem is?!
Thanks in advance!

[kai]

One mistake I've found:

You have s[0] ... s[99].

Code: Select all

    string s[100],s1=""; 

However, when n=100, the program will use s[100].

Code: Select all

       for (int i=1;i<=n;i++)
       {
           do
           {
               cin >> s[i];
           }
           while (s[i].length()!=m);
       }