HDU 4166 & BNU 32715 Robot Navigation (記憶化bfs)

  題意：給一個二維地圖，每個點為障礙或者空地，有一個機器人有三種操作：1、向前走；2、左轉90度；3、右轉90度。現給定起點和終點，問到達終點最短路的條數。   思路：一般的題目只是求最短路的長度，但本題還要求出相應的條數。比賽時只記錄最少的步數，卻沒有記錄以最少步數到達該點的的條數，讓他們一直入隊.......鐵定tle....... 只要記錄好到達該點最少步數的條數，減少了很多重復入隊..........

#include <cstdio>  
#include <cstring>  
#include <iostream>  
#include <string>  
#include <algorithm>  
#include <queue>  
#define MAX 1111  
#define INF 0x7FFFFFFF  
using namespace std;  
  
int n,m,mod;  
struct node {  
    int x,y,dir;  
} st,end;  
  
queue <node> q;  
char map[MAX][MAX];  
int num[MAX][MAX][4]; //步數  
int cnt[MAX][MAX][4]; //多少種路徑以該方向到達該點  
int dx[] = {-1,0,1,0};  
int dy[] = {0,1,0,-1};  
  
void init() {  
    while(!q.empty()) q.pop();  
    memset(num,-1,sizeof(num));  
    memset(cnt,0,sizeof(cnt));  
}  
  
int getdir(char c) {  
    if(c == 'N') return 0;  
    if(c == 'E') return 1;  
    if(c == 'S') return 2;  
    if(c == 'W') return 3;  
}  
  
bool ok(int x,int y) {  
    if(x >= 0 && x < n && y >= 0 && y < m && map[x][y] == '.') return true;  
    return false;  
}  
  
void bfs() {  
    num[st.x][st.y][st.dir] = 0;  
    cnt[st.x][st.y][st.dir] = 1;  
    q.push(st);  
    while(! q.empty()) {  
        node t = q.front();  
        q.pop();  
        node tt;  
        //cout << t.x << ' ' << t.y << ' ' << num[t.x][t.y][t.dir] << endl;  
        for(int i=0; i<4; i++) { //轉方向  
            if(abs(t.dir - i) == 1 || abs(t.dir - i) == 3) {  
                tt = t;  
                if(num[t.x][t.y][i] == -1) {  
                    num[t.x][t.y][i] = num[t.x][t.y][t.dir] + 1;  
                    cnt[t.x][t.y][i] = cnt[t.x][t.y][t.dir];  
                    tt.dir = i;  
                    q.push(tt);  
                } else if(num[t.x][t.y][i] == num[t.x][t.y][t.dir] + 1) {  
                    cnt[t.x][t.y][i] = (cnt[t.x][t.y][i] + cnt[t.x][t.y][t.dir]) % mod;  
                }  
            }  
        }  
        tt = t;  
        tt.x += dx[tt.dir];  
        tt.y += dy[tt.dir];  
        if(ok(tt.x,tt.y)) {  
            if(num[tt.x][tt.y][tt.dir] == -1) { //移動  
                num[tt.x][tt.y][tt.dir] = num[t.x][t.y][t.dir] + 1;  
                cnt[tt.x][tt.y][tt.dir] = cnt[t.x][t.y][t.dir];  
                q.push(tt);  
            } else if(num[tt.x][tt.y][tt.dir] == num[t.x][t.y][t.dir] + 1) {  
                cnt[tt.x][tt.y][tt.dir] = (cnt[tt.x][tt.y][tt.dir] + cnt[t.x][t.y][t.dir]) % mod;  
            }  
        }  
    }  
}  
  
void solve() {  
    int ans = INF;  
    for(int i=0; i<4; i++) {  
        if(num[end.x][end.y][i] != -1) {  
            ans = min(ans,num[end.x][end.y][i]);  
        }  
    }  
    if(ans == INF) {  
        printf("%d -1\n",mod);  
        return ;  
    }  
    int sum = 0;  
    for(int i=0; i<4; i++) {  
        if(num[end.x][end.y][i] == ans) sum = (sum + cnt[end.x][end.y][i]) % mod;  
    }  
    printf("%d %d\n",mod,sum);  
}  
int main() {  
    char c;  
    int ca = 1;  
    while(scanf("%d%d%d",&n,&m,&mod) != EOF) {  
        if(mod == 0) break;  
        init();  
        for(int i=0; i<n; i++) scanf("%s",map[i]);  
        scanf("%d%d%d%d",&st.x,&st.y,&end.x,&end.y);  
        scanf(" %c",&c);  
        st.dir = getdir(c);  
        bfs();  
        printf("Case %d: ",ca++);  
        solve();  
    }  
    return 0;  
}