uva-657-搜索

注意是四个方向(上下左右),不是八个方向,当成了八个方向做,一直wa

AC时间:0ms

#include<stdio.h>

#include<iostream>

#include <strstream>

#include<string>

#include<memory.h>

#include<math.h>

#include<sstream>

#include<queue>

#include<stack>

#include<vector>

using namespace std;

struct DIR

{

	int r;

	int c;

	char cc;

};

const DIR dir[] = { {-1,0},{1,0},{0,-1},{0,1}};

const int MAXR = 60;

void markX(queue<DIR> nq, queue<DIR> &q, char a[][MAXR], int r, int c,

		int used[][MAXR])

{

	DIR d;

	while (!nq.empty())

	{

		d = nq.front();

		nq.pop();

		for (int i = 0; i < 4; i++)

		{

			int nr = d.r + dir[i].r;

			int nc = d.c + dir[i].c;

			if (nr < 0 || nc < 0 || nr == r || nc == c || used[nr][nc] == 1

					|| a[nr][nc] == '.')

				continue;

			used[nr][nc] = 1;

			DIR ddd;

			ddd.r = nr;

			ddd.c = nc;

			ddd.cc = a[nr][nc];

			if (ddd.cc == '*')

			{

				q.push(ddd);

			}

			else

				nq.push(ddd);

		}

	}

}

void bfs(queue<DIR> q, char a[][MAXR], int r, int c, int used[][MAXR],

		int* total)

{

	while (!q.empty())

	{

		DIR dd = q.front();

		q.pop();

		for (int i = 0; i < 4; i++)

		{

			int nr = dd.r + dir[i].r;

			int nc = dd.c + dir[i].c;

			if (nr < 0 || nc < 0 || nr == r || nc == c || used[nr][nc] == 1

					|| a[nr][nc] == '.')

				continue;

			used[nr][nc] = 1;

			DIR ddd;

			ddd.r = nr;

			ddd.c = nc;

			ddd.cc = a[nr][nc];

			if (ddd.cc == '*')

				q.push(ddd);

			else

			{

				queue<DIR> q2;

				q2.push(ddd);

				markX(q2, q, a, r, c, used);

				if(dd.cc=='*')

				(*total)++;

			}

		}

	}

}

int main()

{

	int h, w;

	int tc = 0;

	while (cin >> w >> h)

	{

		tc++;

		if (h == w && h == 0)

			return 0;

		cout << "Throw " << tc << endl;

		char a[MAXR][MAXR];

		int used[MAXR][MAXR];

		memset(a, '.', sizeof(a));

		memset(used, 0, sizeof(used));

		for (int i = 0; i < h; i++)

			for (int j = 0; j < w; j++)

				cin >> a[i][j];

		int t[20];

		memset(t, 0, sizeof(t));

		int length = 0;

		queue<DIR> q1;

		for (int i = 0; i < h; i++)

			for (int j = 0; j < w; j++)

				if (used[i][j] == 0 && a[i][j] == 'X')

				{

					DIR dd;

					dd.r = i;

					dd.c = j;

					dd.cc = a[i][j];

					used[i][j] = 1;

					q1.push(dd);

					int total = 1;

					bfs(q1, a, h, w, used, &total);

					t[length++] = total;

				}

		for (int i = 0; i < length; i++)

			for (int j = 1; j < length; j++)

				if (t[j - 1] > t[j])

				{

					int k = t[j - 1];

					t[j - 1] = t[j];

					t[j] = k;

				}

		for (int i = 0; i < length; i++)

			if (i == 0)

				cout << t[i];

			else

				cout << " " << t[i];

		cout << endl<<endl;;

	}

	return 0;

}