Easy Problem(cdOJ1644)

#include #include #include #include #include #include #include #include #include #include using namespace std; struct my { int left; int right; }stir[1000]; int main() { int i,j,k; char go[100][100]; int num=0; int t; int n,m; cin>>t; while (t--) { num++; cin>>n>>m; for (i=0;i>go[i]; int l,r; stir[0].left=stir[0].right=-1; for (i=0;i

Easy Problem

Time Limit: 1000 ms Memory Limit: 65536 kB Solved:122 Tried: 554

Description

Many students won prizes in UESTC Annual Amateur Contest last year. Yangsir asked Loveqinqin to send prizes to the winners' dormitories. Poor Loveqinqin found that these dormitories were scattered on several different floors of the dorm building. Loveqinqin drew the map of the dorm building as showed in the following picture. Rooms colored red contained winners. Loveqinqin can only go to upstairs throught the stairs at either end of each floor. Assume that it takes Loveqinqin one minute to walk from a room to a neighbour room. Going through the stairs from Floor i to Floor i + 1 also takes one minute. Note that if a room is near to the stairs, the time Loveqinqin needs to walk between stairs and that room is one minute. Loveqinqin could start at either end of the Floor 1 and would stop at either end of the topmost floor. Please find a route which takes the minimum minutes, through which Loveqinqin can send prizes to all winners.

Input

There are multiple test cases. The first line of the input will be an integer T (T <= 100) indicating the number of test cases. For each test case, in the first line there are two numbers: N M, indicating the number of floors (1 <= N <= 100) and the width of each floor (1 <= M <= 100). The following N lines describe the distribution of the winners. The first line is about Floor 1, the second line is about Floor 2, ..., the last line is about Floor N. We use '*' to denote a room containing winners, '.' to denote other rooms, 's' to denote stairs. We guarantee that the width of each floor equals M. The two ends of each lines are the only places where 's' appears.

Output

For each test case, print "Case #t: "first, in which t is the number of the test case starting from 1. Then output the minimum minutes.

Simple Input

4 1 4 s*.s 3 3 s.s s*s s.s 4 4 s*.s s.*s s..s s*.s 4 6 s*...s s..**s s.*..s s..*.s

Simple Output

Case #1: 2 Case #2: 4 Case #3: 11 Case #4: 20

Hint

In the first case, Loveqinqin has to return to one of the ends of the first floor.This is really an easy problem. Come on!!!

Source

10th UESTC Programming Contest Preliminary