TYVJ P1030 乳草的入侵 Label:跳馬問題

背景

USACO?OCT09?6TH

描述

Farmer?John一直努力讓他的草地充滿鮮美多汁的而又健康的牧草。可惜天不從人愿，他在植物大戰人類中敗下陣來。邪惡的乳草已經在他的農場的西北部份佔領了一片立足之地。

草地像往常一樣，被分割成一個高度為Y(1?<=?y?<=?100),?寬度為X(1?<=?x?<=?100)的直角網格。(1,1)是左下角的格（也就是說坐標排布跟一般的X,Y坐標相同）。乳草一開始佔領了格(Mx,My)。每個星期，乳草傳播到已被乳草佔領的格子四面八方的每一個沒有很多石頭的格（包括垂直與水平相鄰的和對角線上相鄰的格）。1周之后，這些新佔領的格又可以把乳草傳播到更多的格裡面了。

Bessie想要在草地被乳草完全佔領之前盡可能的享用所有的牧草。她很好奇到底乳草要多久才能佔領整個草地。如果乳草在0時刻處於格(Mx,My)，那麼還在那個時刻它們可以完全佔領入侵整片草地呢（對給定的數據總是會發生）？

草地由一個圖片表示。"."表示草，而"*"表示大石。比如這個X=4,?Y=3的例子。

?????....
?????..*.
?????.**.

如果乳草一開始在左下角（第1排，第1列），那麼草地的地圖將會以如下態勢發展：


乳草會在4星期后佔領整片土地。

輸入格式

*?第一行:?四個由空格隔開的整數:?X,?Y,?Mx,?My

*?第2到第Y+1行:?數據的第y+1行由X個字符（"."表示草地，"*"表示大石），描述草地的
第(Y+2-y)行。

輸出格式

*?第一行:?一個單獨的整數表示最后一個不是大石塊的格子被乳草佔領的星期數。

測試樣例1

輸入

4 3 1 1?
....?
..*.?
.**.

輸出

4

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int N,M,P,dep,ans,X,Y,map[105][105],
    dx[15]={ 1,1,1, 0,0,-1,-1,-1},
    dy[15]={-1,0,1,-1,1,-1, 0, 1};
char juzhen[105][105];
struct cc{
    int x,y;
}q1;
queue<cc> que; 


void init_(){
    memset(map,-1,sizeof(map));
    scanf("%d%d%d%d",&N,&M,&X,&Y);//M行 N列 
    for(int i=M;i>=1;i--){
        scanf("%s",juzhen[i]+1);
    }
    q1.x=Y;q1.y=X;
    que.push(q1);
    map[Y][X]=0;
}

void print(){
    for(int i=1;i<=M;i++){
        for(int j=1;j<=N;j++){
            printf("%-3d",map[i][j]);
        }
        puts("");
    }
    puts("");
}

int main(){
//    freopen("01.txt","r",stdin);
    init_();
    
    while(!que.empty()){
        q1=que.front();que.pop();
        for(int i=0;i<8;i++){
            int xx=q1.x+dx[i],yy=q1.y+dy[i];
            if(xx<1||yy<1||xx>M||yy>N) continue;
            if(juzhen[xx][yy]=='*') continue;
            if(map[xx][yy]>=0) continue;
            cc q2;q2.x=xx;q2.y=yy;
            que.push(q2);
            map[xx][yy]=map[q1.x][q1.y]+1;
            ans=max(ans,map[xx][yy]);
        }
//        print();
    }
    printf("%d\n",ans);
    return 0;
}

這輸入方式我整個人都不好了，n和m搞混，x和y搞混，

樣例還如此飄逸，根本不知道x和y反了！！！