## 657 - The die is cast

Moderator: Board moderators

faiem
New poster
Posts: 14
Joined: Fri Aug 13, 2010 12:22 pm

### WA: 657 - The die is cast

I dnt know why i getting WA...I passed all I/O in boards...Help me pls..Here is my code..

Code: Select all

``````#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
long t=0;
class Die{

private:
char cast[60][60],ch;
vector<long> v,x,s,sorting;
long I,J;

public:
bool Input(long R,long C)
{
for(I=0;I<R;I++)
{
for(J=0;J<C;J++)
{
cast[I][J]=getchar();
}
getchar();
}
return 1;
}

bool print(long R,long C)
{

for(I=0;I<R;I++){
for(J=0;J<C;J++)
printf("%c",cast[I][J]);
printf("\n");
}
return 0;
}

//(if DFS find any ' * ' make it 'S' )and (if find ' X ' makes it 'Y')

bool X_MAN(long x,long y,long R,long C)  //find 'X'
{
long a,b;
a=x+1;b=y;
if(a>=0&&a<R&&b>=0&&b<C)
{
if(cast[a][b]=='X')
{
cast[a][b]='Y';
v.push_back(a);
v.push_back(b);
return 1;
}
else if(cast[a][b]=='*')
{
s.push_back(a);
s.push_back(b);
return 0;
}

}
a=x-1;b=y;
if(a>=0&&a<R&&b>=0&&b<C)
{
if(cast[a][b]=='X')
{
cast[a][b]='Y';
v.push_back(a);
v.push_back(b);
return 1;
}
else if(cast[a][b]=='*')
{
s.push_back(a);
s.push_back(b);
return 0;
}

}
a=x;b=y+1;
if(a>=0&&a<R&&b>=0&&b<C)
{
if(cast[a][b]=='X')
{
cast[a][b]='Y';
v.push_back(a);
v.push_back(b);
return 1;
}
else if(cast[a][b]=='*')
{
s.push_back(a);
s.push_back(b);
return 0;
}

}
a=x;b=y-1;
if(a>=0&&a<R&&b>=0&&b<C)
{
if(cast[a][b]=='X')
{
cast[a][b]='Y';
v.push_back(a);
v.push_back(b);
return 1;
}
else if(cast[a][b]=='*')
{
s.push_back(a);
s.push_back(b);
return 0;
}

}
return 0;
}

bool star_Man(long x,long y,long R,long C) //find '*'
{
long a,b;
a=x+1;b=y;
if(a>=0&&a<R&&b>=0&&b<C)
{
if(cast[a][b]=='*')
{
cast[a][b]='S';
s.push_back(a);
s.push_back(b);
return 1;
}
else if(cast[a][b]=='X')
{
t++;
v.push_back(a);
v.push_back(b);
X_DFS(R,C);
return 1;
}
}
a=x-1;b=y;
if(a>=0&&a<R&&b>=0&&b<C)
{
if(cast[a][b]=='*')
{
cast[a][b]='S';
s.push_back(a);
s.push_back(b);
return 1;
}
else if(cast[a][b]=='X')
{
t++;
v.push_back(a);
v.push_back(b);
X_DFS(R,C);
return 1;
}
}

a=x;b=y+1;
if(a>=0&&a<R&&b>=0&&b<C)
{
if(cast[a][b]=='*')
{

cast[a][b]='S';
s.push_back(a);
s.push_back(b);
return 1;
}
else if(cast[a][b]=='X')
{
t++;
v.push_back(a);
v.push_back(b);
X_DFS(R,C);
return 1;
}
}

a=x;b=y-1;
if(a>=0&&a<R&&b>=0&&b<C)
{
if(cast[a][b]=='*')
{
cast[a][b]='S';
s.push_back(a);
s.push_back(b);
return 1;
}
else if(cast[a][b]=='X')
{
t++;
v.push_back(a);
v.push_back(b);
X_DFS(R,C);
return 1;
}
}

return 0;
}

bool X_DFS(long R,long C) // 'X' DfS
{
long X,Y;
X=v[v.size()-2];
Y=v[v.size()-1];
cast[X][Y]='Y';

while(!v.empty())
{
X=v[v.size()-2];
Y=v[v.size()-1];
while(X_MAN(X,Y,R,C))
{
X=v[v.size()-2];
Y=v[v.size()-1];
}
v.pop_back();
v.pop_back();
}
return 0;
}
//if DFS find any ' * ' make it 'S' and if find ' X ' makes it 'Y'
bool S_DFS(long R,long C)  // '*' dfs
{
long X,Y;
X=s[s.size()-2];
Y=s[s.size()-1];
cast[X][Y]='S';
while(star_Man(X,Y,R,C))
{
X=s[s.size()-2];
Y=s[s.size()-1];
}
s.pop_back();
s.pop_back();

return 0;
}
bool scan(long R,long C) //scan the whole matrix
{

for(I=0;I<R;I++)
for(J=0;J<C;J++)
if(cast[I][J]=='X')
{
t=1;              //counter to count how many 'X' on a single dice.
v.push_back(I);
v.push_back(J);
X_DFS(R,C);
if( !s.empty() )    //if input ....X.... i mean only X then 'vector s'  is empty so not need another DFS
S_DFS(R,C);
sorting.push_back(t);//total 'X' count for a single dice.
}

sort(sorting.begin(),sorting.end());

if( ! sorting.empty() )  //Print the Sorting Result here...
{
for(I=0;I<sorting.size()-1;I++)
printf("%ld ",sorting[I]);
printf("%ld",sorting.back());
}
else
printf("0");  //I submit without this condition but still WA.
printf("\n");
return 1;
}

};

int main()
{
long R,C,I,J,count=1;
/*
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
*/
while(scanf("%ld %ld",&C,&R)==2)
{
getchar();
if(R==0&&C==0)
break;
Die hard;  //creating obj.
hard.Input(R,C); //taking input...
printf("Throw %ld\n",count);
hard.scan(R,C);  //scan the matrix...
printf("\n");
count++;
}
return 0;
}

``````

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

### Re: 657 - The die is cast

I got WA...
by the way, all the available test cases in this site are have right output...

Code: Select all

``````#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int p[4][2]={{0,-1}, {1,0}, {0,1}, {-1,0}};

vector < string > grid;
bool mark[51][51];
vector < int > res;
int n , m , cnt;

void dfs(int row , int col);

void dfs2(int row , int col)
{
//cout << "dfs2  x = " << row << "  y = " << col << endl;
mark[row][col] = true;
for(int i=0 ; i < 4 ; i++)
{
int rt = row + p[i][0];
int ct = col + p[i][1];
if(rt >= 0 && rt < m && ct >= 0 && ct < n)
{
if(mark[rt][ct] ==  false)
{
if(grid[rt][ct] == 'X')
dfs2(rt , ct);
}
}
}
for(int i=0 ; i < 4 ; i++)
{
int rt = row + p[i][0];
int ct = col + p[i][1];
if(rt >= 0 && rt < m && ct >= 0 && ct < n)
{
if(mark[rt][ct] ==  false)
{
if(grid[rt][ct] == '*')
dfs(rt , ct);
}
}
}
}

void dfs(int row , int col)
{
mark[row][col] = true;
for(int i=0 ; i < 4 ; i++)
{
int rt = row + p[i][0];
int ct = col + p[i][1];
if(rt >= 0 && rt < m && ct >= 0 && ct < n)
{
if(mark[rt][ct] ==  false)
{
if(grid[rt][ct] == 'X')
{
cnt++;
dfs2(rt , ct);
}
if(grid[rt][ct] == '*')
dfs(rt , ct);
}
}
}
}

int main()
{
string tmp;
int ncase = 1;
while(cin >> n >> m , n || m)
{
cnt = 0;
getline(cin , tmp);
grid.clear();
res.clear();
memset(mark , false, sizeof mark);
for( int i=0 ; i < m ; i++)
{
getline(cin , tmp);
grid.push_back(tmp);
}

for(int i = 0 ; i < m ; i++)
{
for(int j = 0 ; j < n ; j++)
{
if(mark[i][j] == false)
{
if(grid[i][j] == '*')
{
res.push_back(cnt);
cnt = 0;
dfs(i , j);
}
if(grid[i][j] == 'X')
{
res.push_back(cnt);
cnt = 1;
dfs2(i , j);
}
}
}
}
if (cnt > 0)
res.push_back(cnt);

printf("Throw %d\n",ncase++);
sort(res.begin()+1 , res.end());
for(int i = 1 ; i < res.size() ; i++)
{
if(i > 1)
cout << " ";
cout << res[i];
}
cout << endl << endl;
}
return 0;
}
``````

New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

### Re: 657 - The die is cast

for people who's still getting WA even with the previous I/O is OK
try this case ...

Code: Select all

``````10 2
..X**X***X
..XXXX....``````

ur output may be
1 1
2

hope this helps

torryton
New poster
Posts: 3
Joined: Thu Nov 10, 2011 12:45 pm

### Re: 657 - The die is cast

Many thanks!!! Just what i needed!! Nice that the problem was finally solved and i can start doing something else

outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

### Re: 657 - The die is cast

try this

Input:

Code: Select all

``````2 2
XX
XX
2 2
..
**
2 2
..
..
5 5
XX**X
XX**X
.....
.....
XX**X``````
Output:

Code: Select all

``````Throw 1
1

Throw 2
0

Throw 3
0

Throw 4
2 2

``````
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 657 - The die is cast

i passed al the sample I/Os here, and my logic seems quite ok. but dont know, why am getiing WA. can any1 help,plz?

Code: Select all

``````AC
``````
Last edited by Scarecrow on Tue Apr 17, 2012 8:21 pm, edited 1 time in total.
Do or do not. There is no try.

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

### Re: 657 - The die is cast

Input:

Code: Select all

``````3 2
XX*
X..
0 0``````
AC Output:

Code: Select all

``````Throw 1
1

``````
Check input and AC output for thousands of problems on uDebug!

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 657 - The die is cast

thnx brianfry713 got AC with ur help
Do or do not. There is no try.

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

### Re: 657 - The die is cast

The picture will contain at least one die

so there is no input for which 0 comes!

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

### Re: 657 - The die is cast

The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive.
Check input and AC output for thousands of problems on uDebug!

Ronok1307
New poster
Posts: 8
Joined: Tue May 29, 2012 7:37 pm

### Re: 657 - The die is cast

Removed
Last edited by Ronok1307 on Mon Jun 04, 2012 9:31 pm, edited 1 time in total.

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

### Re: 657 - The die is cast

Don't use getchar() and count on it to be a newline. That won't work if there are extra spaces in the input file.
Check input and AC output for thousands of problems on uDebug!

SyFyKid
New poster
Posts: 26
Joined: Tue May 08, 2012 9:47 am

### Re: 657 - The die is cast

I am getting crazy solving this problem...

here is my code: http://paste.ubuntu.com/1023130/
I have tested ALL data that I found here... I have checked my algo with all possible and impossible test cases... works OK... but system shows me WA.
Really need help.

Thx.

Code: Select all

``````import java.io.*;
//import java.math.BigInteger;
import java.util.*;
//import java.awt.geom.*;
//import java.util.regex.*;
import java.util.StringTokenizer;

public class Main implements Runnable {
int throwCount = 1;
ArrayList<String> output = new ArrayList<String>();

void solve(){
console(System.getProperty("ONLINE_JUDGE") != null);

while(true){
int y = RI(), x = RI();
if(x==0 && y==0) break;

char[][] image = new char[x][y];
for(int i=0; i<x; i++){
String line = RLine().trim();

for(int j=0; j<y; j++){
image[i][j] = line.charAt(j);
}
}

solve(x, y, image);

++throwCount;
}

for(int i=0; i<output.size()-1; i+=2){
out.println(output.get(i));
out.print(output.get(i+1));

if(i == output.size() - 2){ out.println(); } else out.println("\n");
}
}

void solve(int height, int width, char[][] image){
HashSet<Integer> used = new HashSet<Integer>();
ArrayList<Integer> points = new ArrayList<Integer>();
HashSet<Integer> component;
boolean flag = false;

for(int i=0; i<height; i++){
for(int j=0; j<width; j++){
if(!used.contains(encode(i, j)) && (image[i][j] == 'X' || image[i][j] == '*')){
flag = true;
component = getFullComponent(i, j, used, image);

int dots = countDots(component, image);
}
}
}

if(!flag){
}

Collections.sort(points);

// generating output
StringBuilder sb = new StringBuilder("");

for(int v:points) sb.append(Integer.toString(v)+" ");
}

HashSet<Integer> getFullComponent(int x, int y, HashSet<Integer> used, char[][] image){
HashSet<Integer> component = new HashSet<Integer>();

while(!q.isEmpty()){
int encodedValue = q.poll();
int curX = encodedValue/PRIME, curY = encodedValue%PRIME;

for(int i=0; i<DX4.length; i++){
int newX = curX + DX4[i], newY = curY + DY4[i];

if(newX>=0 && newX<image.length && newY>=0 && newY<image[0].length && !used.contains(encode(newX, newY)) && image[newX][newY]!='.'){
int newEncodedValue = encode(newX, newY);

}
}
}

return component;
}

int countDots(HashSet<Integer> component, char[][] image){
int dots = 0;
HashSet<Integer> localUsed = new HashSet<Integer>();

for(int encodedValue:component){
int x = encodedValue/PRIME, y = encodedValue%PRIME;

if(image[x][y] == '*' || localUsed.contains(encodedValue)) continue;

dots++;

while(!q.isEmpty()){
int curEncodedValue = q.poll();
int curX = curEncodedValue/PRIME, curY = curEncodedValue%PRIME;

for(int i=0; i<DX4.length; i++){
int newX = curX + DX4[i], newY = curY + DY4[i];
int newEncodedValue = encode(newX, newY);

if(!localUsed.contains(newEncodedValue) && newX>=0 && newX<image.length && newY>=0 && newY<image[0].length && image[newX][newY]=='X'){
}
}
}
}

return dots;
}

int encode(int a, int b){
return PRIME*a + b;
}

// ---------------------------------------------------------- TEMPLATE ----------------------------------------------
final int PRIME = 107;
final int[] DX4 = new int[]{-1, 0, +1, 0}, DY4 = new int[]{0, +1, 0, -1};
final int[] DX8 = new int[]{-1, -1, -1, 0, +1, +1, +1, 0}, DY8 = new int[]{-1, 0, +1, +1, +1, 0, -1, -1};

StringTokenizer st;
PrintWriter out;
boolean eof = false;

public static void main(String[] args) {
}

String nextToken(){
while (st == null || !st.hasMoreTokens()) {
try {
} catch (Exception e) {
eof = true;
return null;
}
}
return st.nextToken();
}

String RLine() {
String ret;
try {
} catch (Exception e) {
ret = "";
}
if (ret == null) {
eof = true;
return null;
}
return ret;
}

int RC() {
try {
} catch (Exception e) {
return -1;
}
}

String RS() {
return nextToken();
}

int RI() {
return Integer.parseInt(nextToken());
}

long RL() {
return Long.parseLong(nextToken());
}

double RD() {
return Double.parseDouble(nextToken());
}

void raiseError(){
int k = 10/0;
}

void console(boolean f) {
if (f) {
out = new PrintWriter(new OutputStreamWriter(System.out));
} else {
try {
File input = new File("input.txt");
if (!input.exists()) {
input.createNewFile();
}

out = new PrintWriter(new OutputStreamWriter(new FileOutputStream("output.txt")));
} catch (Exception e) {
e.printStackTrace();
System.exit(111);
}
}
}

@Override
public void run() {
solve();
out.close();
}
}
``````

Ronok1307
New poster
Posts: 8
Joined: Tue May 29, 2012 7:37 pm

### Re: 657 - The die is cast

brianfry713 wrote:Don't use getchar() and count on it to be a newline. That won't work if there are extra spaces in the input file.
Thanks a lot. I changed the scanf-getchar to a gets-sscanf and got AC.

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

### Re: 657 - The die is cast

SyFyKid wrote:I am getting crazy solving this problem...
Don't read and write to a file.
Check input and AC output for thousands of problems on uDebug!