Time Limit: 2 Seconds Memory Limit: 65536 KB
Benny has a spacious farm land to irrigate. The farm land is a rectangle, and is divided into a lot of samll squares. Water pipes are placed in these squares. Different square has a different type of pipe. There are 11 types of pipes, which is marked from A to K, as Figure 1 shows.
Figure 1
Benny has a map of his farm, which is an array of marks denoting the distribution of water pipes over the whole farm. For example, if he has a map
ADC FJK IHE
then the water pipes are distributed like
Figure 2
Several wellsprings are found in the center of some squares, so water can flow along the pipes from one square to another. If water flow crosses one square, the whole farm land in this square is irrigated and will have a good harvest in autumn.
Now Benny wants to know at least how many wellsprings should be found to have the whole farm land irrigated. Can you help him?
Note: In the above example, at least 3 wellsprings are needed, as those red points in Figure 2 show.
Input
There are several test cases! In each test case, the first line contains 2 integers M and N, then M lines follow. In each of these lines, there are N characters, in the range of 'A' to 'K', denoting the type of water pipe over the corresponding square. A negative M or N denotes the end of input, else you can assume 1 <= M, N <= 50.
Output
For each test case, output in one line the least number of wellsprings needed.
Sample Input
2 2 DK HF 3 3 ADC FJK IHE -1 -1
Sample Output
2 3
结题报告:
一道很简单的题目卡了我几天,这的感觉现在自己弱暴了!需要加油了
其实前几天大致的框架就已经搞定,主要是搜索方向搞错了x+1或x-1时应该往上下搜索,而不是左右,前几次就是错在这了,今后一定要注意!
#include<cstdio> #include<cstring> using namespace std; int a[13][4]={ 1,1,0,0, 0,1,1,0, 1,0,0,1, 0,0,1,1, 0,1,0,1, 1,0,1,0, 1,1,1,0, 1,1,0,1, 1,0,1,1, 0,1,1,1, 1,1,1,1 }; const int maxn = 50 + 5; int vis[maxn][maxn], mp[maxn][maxn]; const int dir[4][2] = {0,-1,-1,0,0,1,1,0}; int n,m; void dfs( int x, int y ) { vis[x][y] = 1; for( int i=0; i<4; i++ ) { int xx = x + dir[i][0]; int yy = y + dir[i][1]; if( vis[xx][yy] || xx<0 || xx>=n || yy<0 || yy>=m ) continue; else if( i==0 && a[mp[xx][yy]][2]==1 && a[mp[x][y]][0]==1 ) dfs( xx, yy ); else if( i==1 && a[mp[xx][yy]][3]==1 && a[mp[x][y]][1]==1 ) dfs( xx, yy ); else if( i==2 && a[mp[xx][yy]][0]==1 && a[mp[x][y]][2]==1 ) dfs( xx,yy ); else if( i==3 && a[mp[xx][yy]][1]==1 && a[mp[x][y]][3]==1 ) dfs( xx, yy); } } int main( ) { char str[maxn]; while( scanf( "%d%d",&n,&m )!=EOF ) { if( n==-1 && m==-1) break; for( int i=0; i<n; i++ ) { scanf( "%s",str ); for( int j=0; j<m; j++ ) { mp[i][j] = str[j] - 'A'; } } memset(vis,0,sizeof(vis)); int ans = 0; for( int i=0; i<n; i++ ) { for( int j=0; j<m; j++ ) { if( !vis[i][j] ) { dfs( i, j ); ans++; } } } printf( "%d\n",ans ); } return 0; }
相关推荐
Positioning and Moving Sprinkler Systems for Irrigation
FAO_Irrigation_Drainage_Paper_56(作物腾发量-作物需水量计算指南),英文版
Research on suitable drip irrigation schedule for tomato,TRAN THAI HUNG,Xing Wengang,Drip Irrigation Technique is a basic form of Water Saving Irrigation. Previous researches of drip irrigation ...
Intelligent irrigation system bascom avr code based on atmega8a
BS ISO 24649-2022 Agricultural irrigation equipment.pdf
Positioning and Moving Sprinkler Systems for Irrigation,刘学智,,In this paper, we present a model that minimizes the amount of time required to irrigate a field that is 80 meters by 30 meters under...
Research on infiltration flow and soil moisture dynamics according to soil depth by drip irrigation technique,TRAN THAI HUNG,邢文刚,Drip Irrigation Technique supplies limited water amount into the ...
新版完整标准 BS ISO 24649-2022 Agricultural irrigation equipment.pdf
PNS.BAFS+324-2022_PNS+Solar+Powered+Irrigation+System+–+Specifications.pdf
PNS.BAFS+325-2022_PNS+Solar+Powered+Irrigation+System+–+Methods+of+Test.pdf
arduino-irrigation, 基于GSM的远程灌溉系统远程控制器 irrigationarduino是一个基于gsm的远程灌溉系统控制器。要求这是建立在一个Arduino和一个 SIM900-based GSM屏蔽( 这是一个我用过的eBay链接。),和的GSMlib...
浙江大学CC98论坛灌水机,使用python和PyQt编写
Irrigation_Sys
matlab贪吃蛇代码Irrigation_Extent_Time_Series 使用 Google 地球引擎,使用 Landsat 对爱达荷州蛇河平原的灌溉和非灌溉土地进行分类。 分类基于季节性 NDMI(标准化差异水或水分指数)(也称为 NDWI)的二元分类。...
Tuya IoTOS嵌入式演示WiFi和BLE智能灌溉器 | 介绍 该演示基于Tuya Smart Cloud平台,Tuya Smart APP,IoTOS嵌入式WiFi&Ble ...sh build_app.sh apps/tuya-iotos-embeded-demo-wifi-ble-smart-irrigation tuya-iotos-
Tree-type Irrigation Pipe Network Planning Using an Improved Bat Algorithm
SMART_IRRIGATION使用IOT和机器学习等技术实施的最后一年学术项目-项目思想基本上是实现电子农业应用-used我们使用了weMos D1 mini,Arduino,一些传感器来测量农场中的实时温度,湿度we我们使用了REST API用于...
智能灌溉系统 将土壤传感器的地线与Arduino的地线连接。 将Vcc与Arduino的5v连接。 如果需要此值,则将A0与arduino的模拟引脚(此处为A0)相连,否则可以使用数字引脚。 将您的ardino板连接到pi的usb端口。...
灌溉系统 从世界任何地方控制您的灌溉系统。 要求 Node.js 安装 git clone ... 在仓库的根目录中。 npm install npm start 作者 塔米尔·亨(Tamir Hen)