ACM (UVa) : 10189


Critical Input : 
4 4
*...
.*..
..*.
...*
4 4
****
****
****
****
4 4
....
....
....
....
4 4
*.*.
.*.*
*.*.
.*.*
6 6
......
******
......
******
......
******
1 1
.
1 1
*
1 7
.*.*.*.
7 1
*
.
*
.
*
.
*
0 0

Critical Output :
Field #1:
*210
2*21
12*2
012*

Field #2:
****
****
****
****

Field #3:
0000
0000
0000
0000

Field #4:
*3*2
3*4*
*4*3
2*3*

Field #5:
233332
******
466664
******
466664
******

Field #6:
0

Field #7:
*

Field #8:
1*2*2*1

Field #9:
*
2
*
2
*
2
*
#include <stdio.h>
#include <iostream.h>

int main ()
{
	char A[150][150], Input [150];
	long M, N, I, J, Case=0, Flag = 0;
	//freopen ("10189in", "r", stdin);
	//freopen ("10189out", "w", stdout);

	while (1){

		gets(Input);
		sscanf(Input,"%ld%ld",&M,&N);

		if (M==0 && N==0)
			break;

		long B[150][150] = {0};

		for (I=0; I<M; I++)
			gets (A[I]);

		for (I=0; I<M; I++ ) {

			for (J=0; J<N; J++){

				if (A[I][J]=='*'){
					B[I][J+1]++;
					B[I+1][J+1]++;
					B[I+1][J]++;
					B[I+1][J-1]++;
					B[I][J-1]++;
					B[I-1][J-1]++;
					B[I-1][J]++;
					B[I-1][J+1]++;
				}
			}

		}

		// output
		if (Flag==1)
			printf("\n");
		Flag = 1;
		printf("Field #%ld:\n", ++Case);
		for (I=0; I<M; I++){
			for (J=0; J<N; J++){
				if (A[I][J]=='*')
					printf("%c", A[I][J]);
				else
					printf("%ld", B[I][J]);

			}
			printf("\n");
		}

		//printf("\n");
	}
	return 0;
}

12 thoughts on “ACM (UVa) : 10189

  1. hi,
    i find these test cases by brainstorming 🙂
    Don’t get perplexed, these are not judge input/output
    its my guess that ppls may be caught by those trap.

  2. hey

    could u make me a favor? I dont know what the problem with my coding. it is getting wrong answer. I believe it is having a presentation error. I cant find it.

    please help me.


    #include
    #define MAX_N 1000
    #define MAX_M 100

    bool minesweeper[MAX_N][MAX_M];
    char mine[MAX_N][MAX_M];

    void takeInput(int n,int m)
    {
    char ch;
    int i,j;
    for( i = 0;i <n ;i++)
    for( j =0; j<m ;j++)
    {
    scanf("%c",&ch);
    if(ch=='\n')
    {
    scanf("%c",&ch);
    //printf("\n");
    }

    //printf("%c", ch);
    if(ch=='*')
    minesweeper[i][j]=true;
    else
    minesweeper[i][j]= false;
    }
    }

    void prepareOutput(int n, int m)
    {
    int count,i,j;
    //for 0,0
    if(minesweeper[0][0])
    mine[0][0]='*';
    else
    {
    count =0;
    if(minesweeper[0][1])
    ++count;
    if(minesweeper[1][0])
    ++count;
    if(minesweeper[1][1])
    ++count;
    mine[0][0]=count+'0';
    }
    //for cell with index : 0,m-1
    if(minesweeper[0][m-1])
    mine[0][m-1]='*';
    else
    {
    count =0;
    if(minesweeper[0][m-2])
    ++count;
    if(minesweeper[1][m-1])
    ++count;
    if(minesweeper[1][m-2])
    ++count;
    mine[0][m-1]=count+'0';
    }
    //for n-1,0
    if(minesweeper[n-1][0])
    mine[n-1][0]='*';
    else
    {
    count =0;
    if(minesweeper[n-2][0])
    ++count;
    if(minesweeper[n-2][1])
    ++count;
    if(minesweeper[n-1][1])
    ++count;
    mine[n-1][0]=count+'0';
    }
    //for cell having highest row and highest col
    if(minesweeper[n-1][m-1])
    mine[n-1][m-1]='*';
    else
    {
    count =0;
    if(minesweeper[n-1][m-2])
    ++count;
    if(minesweeper[n-2][m-2])
    ++count;
    if(minesweeper[n-2][m-1])
    ++count;
    mine[n-1][m-1]=count+'0';
    }

    //for cells in first col
    for(i=1;i<=n-2;i++)
    {
    j=0;
    if(minesweeper[i][0])
    mine[i][0]='*';
    else
    {
    count =0 ;
    if(minesweeper[i-1][j+1])
    ++count;
    if(minesweeper[i-1][j])
    ++count;

    if(minesweeper[i][j+1])
    ++count;

    if(minesweeper[i+1][j+1])
    ++count;
    if(minesweeper[i+1][j])
    ++count;

    mine[i][0]=count+'0';
    }

    }
    //for cells in last col
    for(i=1;i<=n-2;i++)
    {
    j=m-1;
    if(minesweeper[i][m-1])
    mine[i][m-1]='*';
    else
    {
    count =0 ;

    if(minesweeper[i-1][j])
    ++count;
    if(minesweeper[i][j-1])
    ++count;
    if(minesweeper[i+1][j-1])
    ++count;
    if(minesweeper[i+1][j])
    ++count;
    if(minesweeper[i-1][j-1])
    ++count;
    mine[i][m-1]=count+'0';
    }

    }

    //for cells in first row
    for(j=1;j<=m-2;j++)
    {
    i=0;
    if(minesweeper[i][j])
    mine[0][j]='*';
    else
    {
    count =0 ;

    if(minesweeper[i][j-1])
    ++count;
    if(minesweeper[i][j+1])
    ++count;
    if(minesweeper[i+1][j-1])
    ++count;
    if(minesweeper[i+1][j+1])
    ++count;
    if(minesweeper[i+1][j])
    ++count;

    mine[i][j]=count+'0';
    }

    }
    //for cells in last row
    for(j=1;j<=m-2;j++)
    {
    i=n-1;
    if(minesweeper[i][j])
    mine[i][j]='*';
    else
    {
    count =0 ;
    if(minesweeper[i-1][j+1])
    ++count;
    if(minesweeper[i-1][j])
    ++count;
    if(minesweeper[i][j-1])
    ++count;
    if(minesweeper[i][j+1])
    ++count;

    if(minesweeper[i-1][j-1])
    ++count;
    mine[i][j]=count+'0';
    }

    }

    //for cell having eight neibor
    for(i=1;i<n-1;i++)
    for( j=1;j<m-1;j++)
    {
    count =0;
    if(!minesweeper[i][j])
    {

    if(minesweeper[i-1][j-1])
    ++count;
    if(minesweeper[i-1][j+1])
    ++count;
    if(minesweeper[i-1][j])
    ++count;
    if(minesweeper[i][j-1])
    ++count;
    if(minesweeper[i][j+1])
    ++count;
    if(minesweeper[i+1][j-1])
    ++count;
    if(minesweeper[i+1][j+1])
    ++count;
    if(minesweeper[i+1][j])
    ++count;
    mine[i][j]=count+'0';

    }//end of if
    else
    mine[i][j] = '*';
    }//end of for loop
    }

    void printOutput(int numset,int n, int m)
    {
    if(numset!=1)
    printf("\n\n");
    printf("Field #%d:",numset);
    int i, j;
    for( i=0;i<n;i++)
    {
    printf("\n");
    for( j=0;j<m;j++)
    if(mine[i][j]=='*')
    printf("*");
    else
    printf("%d",mine[i][j]-'0');

    }
    }

    int main()
    {

    //freopen("input.txt","r",stdin);

    int m,n,numSet=0;
    while(scanf("%d%d",&n,&m)==2)
    {

    if(!m && !n)
    {
    printf("\n");
    break;

    }
    takeInput(n,m);
    prepareOutput(n,m);
    printOutput(++numSet,n,m);
    }

    return 0;
    }

  3. @tanvir,
    you are right, you have some problems with the input and output
    thats why u will get presentation error
    but u have some problems with your logic too
    for example, look at the following code segment:

    if(minesweeper[n-1][0])
            mine[n-1][0]='*';
        else
        {
            count =0;
            if(minesweeper[n-2][0])
                ++count;
            if(minesweeper[n-2][1])
                ++count;
            if(minesweeper[n-1][1])
                ++count;
            mine[n-1][0]=count+'0';
        }
    

    if n == 1 then what will be the value of minesweeper[n-2][0]?
    its out of the limit of array

    another thing:
    printOutput function should be write as follows

    void printOutput(int numset,int n, int m)
    {
        if(numset!=1)
            printf("\n");
        printf("Field #%d:\n",numset);
        int i, j;
        for( i=0;i<n;i++)
        {
            for( j=0;j<m;j++)
                if(mine[i][j]=='*')
                    printf("*");
                else
                    printf("%d",mine[i][j]-'0');
            printf ("\n");
        }
    }
    

    one last thing, try to take your input by a string/character array

  4. Could you help me out? I just can’t figure out why my code wont get accepted, I’ve tried it with all of your inputs and it works just fine:

    #include
    #include

    #define BOMB INT_MIN
    #define max(a,b) ((a) > (b) ? (a) : (b))

    #define min(a,b) ((a) > (b) ? (b) : (a))

    /* field stands for the bidimentional array */
    /* n stands for the number or lines of the array */
    /* m stands for the number of columns of the array */

    void placeNumbers(int *const field[], int n, int m)
    { int i, j, k, l, topMargin, bottomMargin, leftMargin, rightMargin;

    for(i = 0; i < n; i++)
    { for(j = 0; j < m; j++)
    { if(field[i][j] < 0) /* it's a bomb! */
    { topMargin = max(0, i – 1);
    bottomMargin = min(n – 1, i + 1);
    for(k = topMargin; k <= bottomMargin; k++)
    { leftMargin = max(0, j – 1);
    rightMargin = min(m – 1, j + 1);
    for(l = leftMargin; l <= rightMargin; l++)
    { field[k][l] += 1;
    }
    }
    }
    }
    }
    }

    int main ()
    { int n = 0, m = 0;
    int fieldNum = 0;
    scanf("%d %d", &n, &m);
    while(n != 0 || m != 0)
    { int field[n][m];
    fieldNum++;
    int i, j;
    for(i = 0; i < n; i++)
    { for(j = 0; j < m; j++)
    { char c;
    scanf(" %c", &c);
    if(c == '*')
    { field[i][j] = BOMB;
    }
    else /* c == '.' */
    { field[i][j] = 0;
    }
    }
    }
    int *fields[n];
    for(i = 0; i < n; i++)
    { fields[i] = (int *) field + (i * m); /* = &field[i][0] */
    }

    placeNumbers(fields, n, m);
    printf("Field #%d:\n", fieldNum);
    for(i = 0; i < n; i++)
    {
    for(j = 0; j = 0)
    { printf(“%c”, (char)((int) ‘0’ + fields[i][j]));
    }
    else
    { printf(“*”);
    }
    }
    printf(“\n”);
    }
    printf(“\n”);
    scanf(“%d %d”, &n, &m);
    }

    return 0;
    }

  5. @Felix
    sorry i don’t understand your code .. i think there are some char missing .. you can mail me your code, i will try to help you out .. thank you 🙂

  6. i got WA what could be wrong with my code?

    #include
    #include
    int main(void) {
    int m = 0,n = 0;
    int i = 0,j = 0;
    char mine[105][105];
    int newM[105][105];
    int t = 0;
    while(scanf(“%d %d”,&m, &n)!= EOF ){
    if(t)printf(“\n”);
    if(!m && !n)
    return 0;
    memset(mine, 0, sizeof(mine));
    memset(newM, 0, sizeof(newM));
    if( 0 < n,m <=100){
    for(i=0;i<m;i++)scanf("%s",mine[i]);
    t++;
    printf("Field #%d:",t);
    printf("\n");
    for(i=0;i<m;i++){
    for(j=0;j<n;j++){
    if(mine[i][j] == '.'){
    if(mine[i][j+1] == '*')newM[i][j]+=1;
    if(mine[i][j-1] == '*')newM[i][j]+=1;

    if(mine[i+1][j] == '*')newM[i][j]+=1;
    if(mine[i+1][j-1] == '*')newM[i][j]+=1;
    if(mine[i+1][j+1] == '*')newM[i][j]+=1;

    if(mine[i-1][j] == '*')newM[i][j]+=1;
    if(mine[i-1][j+1] == '*')newM[i][j]+=1;
    if(mine[i-1][j-1] == '*')newM[i][j]+=1;
    printf("%d",newM[i][j]);
    }
    else {if (mine[i][j] == '*')printf("*"); else {printf("%c",mine[i][j]);}}
    }
    printf("\n");
    }
    }
    }
    return 0;
    }

  7. Are you sure about your code is correct? In C++, it produce wrong answer for corner index(e.g. i = 0, j = 0, i = M-1, j = N-1).
    Correct me, if I am wrong.

  8. I don’t know why this doesn’t work:
    #include
    #include
    #include
    using namespace std;

    const int N = 200;
    const int nmoves = 8;
    const pair moves[nmoves] = {make_pair(0, 1), make_pair(0, -1), make_pair(1, 0), make_pair(-1, 0), make_pair(1, 1), make_pair(1, -1), make_pair(-1, 1), make_pair(-1, -1)};

    int grid[N][N];
    char mines[N][N];

    void minesweeper (int n, int m) {
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++) {
    if(grid[i][j] == '*')
    for(int k = 0; k < nmoves; k++)
    if (grid[i + moves[k].first][j + moves[k].second] != '*')
    grid[i + moves[k].first][j + moves[k].second]++;
    }
    }

    int main(int argc, char *argv[]) {
    int n, m, count = 1;
    freopen("data.txt", "w", stdout);
    while ( 1 ) {
    scanf("%d %d", &n, &m);

    if (n == 0 || m == 0) break;
    if (count != 1) printf("\n");
    memset(grid, 0, sizeof(grid));
    memset(mines, 0, sizeof(mines));

    for (int i = 1; i <= n; ++i)
    for(int j = 1; j <= m; j++) {
    scanf("%1s", &mines[i][j]);
    if(mines[i][j] == '*')
    grid[i][j] = '*';
    }

    minesweeper(n, m);

    printf("Field #%d:\n", count++);
    for (int i = 1; i <= n; ++i) {
    for(int j = 1; j <= m; j++)
    if(grid[i][j] == '*') printf("*");
    else printf("%d", grid[i][j]);
    printf("\n");
    }
    }
    return 0;
    }

  9. My algorithm is very simple.
    my code shows the exact answers in all your critical inputs and also in the critical input of Uva but still i get WA
    #include
    #include
    int main()
    {
    int row,col,i,j,r,c,count,cr,cc,t=1,l=2;
    scanf(“%d%d”,&row,&col);
    while(row||col)
    {
    scanf(“%d%d”,&row,&col);
    if(row==0 && col==0)break;
    char mat[row][col];
    for(i=0;i<row;i++)
    {
    scanf("%s",mat[i]);
    }
    printf("Field #%d:\n",t);
    for(r=0;r<row;r++)
    {
    for(c=0;c<col;c++)
    {
    if(mat[r][c]=='*')printf("*");
    else
    {
    count=0;
    for(i=-1;i<2;i++)
    {
    for(j=-1;j-1&&cc>-1)&&(cr<row&&cc<col))
    {
    if(cr==r && cc==c)continue;
    else if(mat[cr][cc]=='*')count++;
    }
    }
    }
    printf("%d",count);
    }
    }
    printf("\n");
    }
    t++;
    scanf("%d%d",&row,&col);
    printf("\n");
    }
    return 0;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s