10603 - Fill

[shi562217697]

Hi,
I got WA for this.Why?

Code: Select all

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#include <set>

using namespace std;

struct state
{
	int water[3];
	int amt;
};
int cap[3];
int d;
int r_d;
int r_cnt;
int hash[201][201];

void read_input()
{
	scanf("%d%d%d%d",&cap[0],&cap[1],&cap[2],&d);
	r_d = r_cnt = 0;
	memset(hash,-1,sizeof(hash));
}

bool is_visited(state& s)
{
	int tmp = hash[s.water[0]][s.water[1]];
	if (tmp != -1 && s.amt >= tmp)
	{
		return true;
	}
	return false;
}
void set_visit(state& s)
{
	hash[s.water[0]][s.water[1]] = s.amt;
}

void bfs()
{
	queue<state> q;
	state tmp;
	tmp.water[0] = tmp.water[1] = tmp.amt = 0;
	tmp.water[2] = cap[2];
	q.push(tmp);
	while (!q.empty())
	{
		state tmp = q.front();
		q.pop();
		if (is_visited(tmp))
		{
			continue;
		}
		set_visit(tmp);

		int max_liter = -1;
		for (int k = 0 ; k < 3 ; ++k)
		{
			if (max_liter == -1 && tmp.water[k] <= d)
			{
				max_liter = tmp.water[k];
			}
			else if (tmp.water[k] <= d && tmp.water[k] > max_liter)
			{
				max_liter = tmp.water[k];
			}
		}
		if (max_liter <= d)
		{
			if (max_liter > r_d)
			{
				r_d = max_liter;
				r_cnt = tmp.amt;
			}
		}

		for (int i = 0 ; i < 3 ; ++i)
		{
			if (tmp.water[i] == 0)
			{
				continue;
			}
			for (int j = 0 ; j < 3 ; ++j)
			{
				if (i == j)
				{
					continue;
				}
				if (tmp.water[j] < cap[j])
				{
					state next;
					memcpy(&next,&tmp,sizeof(next));
					int cnt = next.water[i] < (cap[j] - next.water[j]) ? next.water[i] : (cap[j] - next.water[j]);
					next.water[i] -= cnt;
					next.water[j] += cnt;
					next.amt += cnt;
					q.push(next);
				}
			}
		}
	}
}




int main()
{

#ifdef shichun
	freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
#endif

	int n;
	scanf("%d",&n);
	while (n--)
	{
		read_input();
		bfs();
		printf("%d %d\n",r_cnt,r_d);
	}

	
 	return 0;
}

[lighted]

Your program gives wrong answers for input

Code: Select all

8
102 7 109 33
16 116 148 52
121 61 159 140
1 15 17 10
2 13 17 9
14 2 16 11
1 11 13 10
1 7 8 3

My acc output is

Code: Select all

757 33
176 52
6912 140
13 10
14 9
10 10
5 10
6 3

[shi562217697]

Thanks.I have found the wrong place.

Code: Select all

      if (max_liter <= d)
      {
         if (max_liter > r_d)
         {
            r_d = max_liter;
            r_cnt = tmp.amt;
         }
      }

should be

Code: Select all

      if (max_liter <= d)
      {
         if (max_liter > r_d)
         {
            r_d = max_liter;
            r_cnt = tmp.amt;
         }
         else if ( max_liter == r_d)
        {
            r_cnt = tmp.amt;
        }
      }

[lighted]

I think it will be good if you remove your code after getting accepted

[Zyaad Jaunnoo]

I also keep a bool array of size 201*201*201 that tracks if a state has been visited, initialized to all false.

In fact, only an array of size 201*201 is sufficient to keep track of the visited states.