526互联

NOJ[1144] 农场灌溉问题

发布时间 2023-09-26 22:16:49作者: hello_33

描述：

一农场由图所示的十一种小方块组成，蓝色线条为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。

image

输入：

给出若干由字母表示的最大不超过50×50具体由(m，n)表示，的农场图

输出：

编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。

输入样例：

2 2
DK
HF
3 3
ADC
FJK
IHE
-1 -1

输出样例：

2
3

题解

#include <iostream>
#include <cstring>
using namespace std;

int m, n;
char a[51][51];
int da[4] = {0, 1, 1, 0};
int db[4] = {1, 1, 0, 0};
int dc[4] = {0, 0, 1, 1};
int dd[4] = {1, 0, 0, 1};
int de[4] = {0, 1, 0, 1};
int df[4] = {1, 0, 1, 0};
int dg[4] = {1, 1, 1, 0};
int dh[4] = {0, 1, 1, 1};
int di[4] = {1, 0, 1, 1};
int dj[4] = {1, 1, 0, 1};
int dk[4] = {1, 1, 1, 1};
int cnt = 0;
int used[51][51];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};

int dfs(int x, int y);
int go(int nx, int ny, int direction);

int main()
{
	cin >> m >> n;
	while (m != -1 || n != -1)
	{
		for (int i = 1; i <= m; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				cin >> a[i][j];
			}
		}
		memset(used, 0, sizeof(used));
		for (int row = 1; row <= m; row++)
		{
			for (int col = 1; col <= n; col++)
			{
				if (used[row][col] == 0)
					cnt++;
				dfs(row, col);
			}
		}
		cout << cnt << endl;
		cnt = 0;
		cin >> m >> n;
	}
}

int dfs(int x, int y)
{
	if (x < 1 || x > m || y < 1 || y > n)
		return 0;
	if (used[x][y] == 1)
		return 0;
	used[x][y] = 1;
	for (int i = 0; i < 4; i++)
	{
		if (a[x][y] == 'A' && da[i] == 1)
			if (go(x+dx[i], y+dy[i], i) == 1)
				dfs(x+dx[i], y+dy[i]);
		if (a[x][y] == 'B' && db[i] == 1)
                        if (go(x+dx[i], y+dy[i], i) == 1)
                                dfs(x+dx[i], y+dy[i]);
		if (a[x][y] == 'C' && dc[i] == 1)
                        if (go(x+dx[i], y+dy[i], i) == 1)
                                dfs(x+dx[i], y+dy[i]);
                if (a[x][y] == 'D' && dd[i] == 1)
                        if (go(x+dx[i], y+dy[i], i) == 1)
                                dfs(x+dx[i], y+dy[i]);
		if (a[x][y] == 'E' && de[i] == 1)
                        if (go(x+dx[i], y+dy[i], i) == 1)
                                dfs(x+dx[i], y+dy[i]);
                if (a[x][y] == 'F' && df[i] == 1)
                        if (go(x+dx[i], y+dy[i], i) == 1)
                                dfs(x+dx[i], y+dy[i]);
		if (a[x][y] == 'G' && dg[i] == 1)
                        if (go(x+dx[i], y+dy[i], i) == 1)
                                dfs(x+dx[i], y+dy[i]);
                if (a[x][y] == 'H' && dh[i] == 1)
                        if (go(x+dx[i], y+dy[i], i) == 1)
                                dfs(x+dx[i], y+dy[i]);
		if (a[x][y] == 'I' && di[i] == 1)
                        if (go(x+dx[i], y+dy[i], i) == 1)
                                dfs(x+dx[i], y+dy[i]);
                if (a[x][y] == 'J' && dj[i] == 1)
                        if (go(x+dx[i], y+dy[i], i) == 1)
                                dfs(x+dx[i], y+dy[i]);
		if (a[x][y] == 'K' && dk[i] == 1)
                        if (go(x+dx[i], y+dy[i], i) == 1)
                                dfs(x+dx[i], y+dy[i]);
	}
	return 1;
}

int go(int nx, int ny, int direction)
{
	int dir = (direction + 2) % 4;
	if (a[nx][ny] == 'A')
		return da[dir];
	if (a[nx][ny] == 'B')
		return db[dir];
	if (a[nx][ny] == 'C')
                return dc[dir];
        if (a[nx][ny] == 'D')
                return dd[dir];
        if (a[nx][ny] == 'E')
                return de[dir];
        if (a[nx][ny] == 'F')
                return df[dir];
        if (a[nx][ny] == 'G')
                return dg[dir];
        if (a[nx][ny] == 'H')
                return dh[dir];
        if (a[nx][ny] == 'I')
                return di[dir];
        if (a[nx][ny] == 'J')
                return dj[dir];
	if (a[nx][ny] == 'K')
                return dk[dir];
}