1144.农场灌溉问题

1144.农场灌溉问题

时限：1000ms 内存限制：10000K  总时限：3000ms

描述

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

输入

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

输出

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

输入样例

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

输出样例

2 3

提示

参考迷宫问题，实现时关键要解决好各块的表示问题。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{int dir[4];//上右左下
}s[11];
int m,n;//行列
char map[51][51];
int book[51][51];
int step[4][2]={
   {-1,0},{0,1},{0,-1},{1,0}};
void init()
{for(int i=0;i<11;i++)for(int j=0;j<4;j++){s[i].dir[j]=1;}s[0].dir[1]=0;s[0].dir[3]=0;s[1].dir[3]=0;s[1].dir[2]=0;s[2].dir[0]=0;s[2].dir[1]=0;s[3].dir[0]=0;s[3].dir[2]=0;s[4].dir[2]=0;s[4].dir[1]=0;s[5].dir[0]=0;s[5].dir[3]=0;s[6].dir[3]=0;s[7].dir[1]=0;s[8].dir[0]=0;s[9].dir[2]=0;
}
void dfs(int i,int j)
{int x,y;for(int k=0;k<4;k++){x=step[k][0]+i;y=step[k][1]+j;if(x<0||x>=m||y<0||y>=n)continue;if((s[map[i][j]-'A'].dir[k]+s[map[x][y]-'A'].dir[3-k]==2)&&!book[x][y]){book[x][y]=1;dfs(x,y);}}
}
int main()
{init();int num;while(cin>>m>>n){if(m==-1&&n==-1)break;num=0;memset(book,0,sizeof(book));for(int i=0;i<m;i++)cin>>map[i];for(int i=0;i<m;i++)for(int j=0;j<n;j++){if(book[i][j]==0){num++;book[i][j]=1;dfs(i,j);}}cout<<num<<endl;}return 0;
}