A -?貓捉老鼠 Time Limit:1000MS?????Memory Limit:32768KB?????64bit IO Format:%I64d & %I64u Submit?Status?Practice?FZU 1019

Description

一只貓和一只老鼠在10*10的迷宮中。迷宮中的每個(gè)方格可以是空的，或者含有障礙。貓和老鼠可以進(jìn)入任意一個(gè)空的方格中。當(dāng)他們相遇時(shí)，貓和老鼠在同一個(gè)方格中。但是，無論貓或老鼠都不能進(jìn)入有障礙的方格。我們可以用字符組成的二維數(shù)組表示迷宮，如下圖所示。

老鼠在迷宮中按照一種固定的方式行走：每個(gè)時(shí)刻，老鼠都向它所面對的方向前進(jìn)一格，這需要花費(fèi)１秒時(shí)間。如果前方是一個(gè)障礙或者是迷宮的邊界，它將花１秒的時(shí)間按順時(shí)針方向轉(zhuǎn)90度。

為了抓到老鼠，這只貓決定也按照與老鼠相同的行走方式行進(jìn)。

貓和老鼠在每個(gè)單位時(shí)間內(nèi)是同時(shí)行動(dòng)的。因此，如果貓和老鼠在行進(jìn)過程中“擦肩而過”，貓是無法捉到老鼠的。只有當(dāng)貓和老鼠同時(shí)到達(dá)一個(gè)相同的格子時(shí)，貓才能捉住老鼠。?
初始時(shí)，貓和老鼠不會(huì)在同一個(gè)方格中。并且它們都面向北方。
你的任務(wù)是編一個(gè)程序，求出貓捉到老鼠的所花時(shí)間。

Input

輸入數(shù)據(jù)的第一行n，表示輸入數(shù)據(jù)的組數(shù)。
每組數(shù)據(jù)由10行組成，每行10個(gè)字符，表示迷宮的地圖以及貓和老鼠的初始位置。輸入數(shù)據(jù)保證只有一只貓和一只老鼠。
每組輸入數(shù)據(jù)之后均有一個(gè)空行作為間隔。?

Output

對于每組給定的輸入，輸出一行僅含一個(gè)數(shù)，即貓捉到老鼠所花的時(shí)間。如果貓永遠(yuǎn)都無法抓到老鼠，則輸出0。

Sample Input

1 *...*..... ......*... ...*...*.. .......... ...*.c.... *.....*... ...*...... ..m......* ...*.*.... .*.*......

Sample Output

49 AC Code: //Memory: 228 KB Time: 0 MS //Language: GNU C++ Result: Accepted#include <iostream> #include <cstdio> using namespace std;struct Point {int x, y; }mou, cat; //mouse，cat的坐標(biāo) int dm, dc; //分別為mouse和cat面朝的方向,0北，1東，2南，3西 char map[10][11]; //切記預(yù)留一位存儲‘\0’！T_T int t;//時(shí)間void Move (Point &animal, int &d) {int X,Y;if (d == 0){X = animal.x, Y = animal.y;if(!Y || map[Y-1][X] == '*')d++;elseanimal.y--;}else if (d == 1){X = animal.x+1, Y = animal.y;if (map[Y][X] == '\0' || map[Y][X] == '*')d++;elseanimal.x++;}else if(d == 2){X=animal.x, Y=animal.y;if(Y==9 || map[Y+1][X]=='*')d++;elseanimal.y++;}else{X=animal.x, Y=animal.y;if(!X || map[Y][X-1] == '*')d = 0;elseanimal.x--;} }int main() {int T;scanf("%d",&T);while(T--){t = dm = dc = 0;for(int i = 0; i < 10; i++){scanf("%s", map[i]);}for(int i = 0; i < 10; i++)for(int j = 0; j < 10; j++){if(map[i][j] == 'c'){cat.y = i;cat.x = j;}if(map[i][j] == 'm'){mou.y = i;mou.x = j;}}while (1){t++;Move (cat, dc);Move (mou, dm);if (cat.x == mou.x && cat.y == mou.y) break;if (t > 500){t = 0;break;}}printf ("%d\n", t);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/cszlg/archive/2012/08/03/2910583.html

總結(jié)

以上是生活随笔為你收集整理的FZU 1019猫捉老鼠的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。