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

Post Reply
jdmetz
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA

indexing off the edges

Post by 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)
New poster
Posts: 18
Joined: Fri Jan 07, 2005 9:35 pm
Location: Bangladesh

Post by 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;
}
fuad

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

still not correct..

Post by 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
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

10189 (Minesweeper) - PE, help plz..........

Post by 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
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Post by 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
New poster
Posts: 2
Joined: Mon Jan 03, 2005 8:04 pm

Post by 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
New poster
Posts: 9
Joined: Tue Nov 29, 2005 5:27 pm
Location: Karlsruhe, Germany

10189 (Minesweeper): WA

Post by 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 */
Last edited by SP8472 on Tue Nov 29, 2005 9:18 pm, edited 1 time in total.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

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

SP8472
New poster
Posts: 9
Joined: Tue Nov 29, 2005 5:27 pm
Location: Karlsruhe, Germany

Post by 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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

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

SP8472
New poster
Posts: 9
Joined: Tue Nov 29, 2005 5:27 pm
Location: Karlsruhe, Germany

Post by 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
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby »

thanx Rocky
Sorry for the late reply...

SigmaJargon
New poster
Posts: 2
Joined: Tue Jan 24, 2006 2:39 am
Contact:

10189 in Java - WA?

Post by 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
New poster
Posts: 6
Joined: Mon Mar 06, 2006 10:32 pm

10189 Minesweeper; Runtime Error

Post by 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
New poster
Posts: 5
Joined: Mon Aug 08, 2005 2:36 pm
Location: Japan

Post by 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);
       }

Post Reply

Return to “Volume 101 (10100-10199)”