LightOJ 1389 - Scarecrow【模拟】

痛定思痛。 2022-08-21 11:50 21阅读 0赞

1389 - Scarecrow

<table> 
 <tbody> 
  <tr> 
   <td title="normal judge" style="color:rgb(79,107,114)"><a href="http://lightoj.com/volume_submit.php?problem=1389" style="color:rgb(79,107,114)" rel="nofollow"><img src="http://lightoj.com/images/submit1.png" alt="">&nbsp;</a>&nbsp;&nbsp;<a href="http://udebug.com/LOJ/1389" style="color:rgb(79,107,114)" rel="nofollow"><img src="http://lightoj.com/images/udebug.png" alt=""></a></td> 
   <td style="color:rgb(79,107,114)"><a href="http://lightoj.com/volume_showproblem.php?problem=1389&amp;language=english&amp;type=pdf" style="color:rgb(79,107,114)" rel="nofollow">PDF (English)</a></td> 
   <td style="color:rgb(79,107,114)"><a href="http://lightoj.com/volume_problemstat.php?problem=1389" style="color:rgb(79,107,114)" rel="nofollow">Statistics</a></td> 
   <td style="color:rgb(79,107,114)"><a href="http://lightoj.com/forum_showproblem.php?problem=1389" style="color:rgb(79,107,114)" rel="nofollow">Forum</a></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td style="color:rgb(121,114,104); background:rgb(245,250,250)">Time Limit:&nbsp;<span style="color:rgb(180,95,4)">2 second(s)</span></td> 
   <td style="color:rgb(121,114,104); background:rgb(245,250,250)">Memory Limit:&nbsp;<span style="color:rgb(180,95,4)">32 MB</span></td> 
  </tr> 
 </tbody> 
</table>

![a.jpg][]Taso owns a very long field. He plans to grow different types of crops in the upcoming growing season. The area, however, is full of crows and Taso fears that they might feed on most of the crops. For this reason, he has decided to place some scarecrows at different locations of the field.

The field can be modeled as a **1 x N** grid. Some parts of the field are infertile and that means you cannot grow any crops on them. A scarecrow, when placed on a spot, covers the cell to its immediate left and right along with the cell it is on.

Given the description of the field, what is the minimum number of scarecrows that needs to be placed so that all the useful section of the field is covered? Useful section refers to cells where crops can be grown.

# Input #

Input starts with an integer **T (≤ 50)**, denoting the number of test cases.

Each case starts with a line containing an integer **N (0 < N < 100)**. The next line contains **N** characters that describe the field. A dot **(.)** indicates a crop-growing spot and a hash **(\#)** indicates an infertile region.

# Output #

For each case, print the case number and the number of scarecrows that need to be placed.

<table> 
 <tbody> 
  <tr> 
   <td> <h1 style="color:green">Sample Input</h1> </td> 
   <td> <h1 style="color:green">Output for Sample Input</h1> </td> 
  </tr> 
  <tr> 
   <td> <p>3</p> <p>3</p> <p>.#.</p> <p>11</p> <p>...##....##</p> <p>2</p> <p>##</p> </td> 
   <td> <p>Case 1: 1</p> <p>Case 2: 3</p> <p>Case 3: 0</p> </td> 
  </tr> 
 </tbody> 
</table>

--------------------

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    char map[1000];
    int vis[10000];
    int main()
    {
    	int t;
    	scanf("%d",&t);
    	int tt=0; 
    	while(t--)
    	{
    		memset(vis,0,sizeof(vis));
    		int n;
    		scanf("%d",&n);
    		scanf("%s",map);
    		int len=strlen(map);
    		printf("Case %d: ",++tt);
    		int ans=0;
    		if(strcmp(map,".")==0)
    		{
    			printf("1\n");
    			continue;
    		}
    		for(int i=0;i<len;)
    		{
    			if(map[i]=='.')
    			{
    				ans++;
    				i+=3;
    			}
    			if(map[i]=='#')
    			{
    				i++;
    			}
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

[a.jpg]: /images/20220724/dfa73f9d5bec419a870a7e67e93c7687.png