1 条题解
-
0xuyifeng LV 10 MOD @ 2017-08-20 20:58:37
-----------------------------------------------AC code-----------------------------------------------
#include<cstdio> #include<cstring> #include<iostream> #include<queue> #include<vector> #ifdef WIN32 # define outl "%I64d" #else # define outl "%lld" #endif #define trans(x, y) ((x-1)*n+y) using namespace std; typedef long long LL; const int INF = 1<<30; const int MAXN = 55; int n, m, g[MAXN][MAXN], st, ed; int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}; int dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; struct Edge{ int nxt, to, dis; }edge[100010]; int head[MAXN*MAXN], edge_num; bool con[MAXN*MAXN][MAXN*MAXN]; void add_edge(int from, int to){ edge[++edge_num].nxt = head[from]; edge[edge_num].to = to; head[from] = edge_num; con[from][to] = 1; } bool vis[MAXN][MAXN]; void dfs(int x, int y, int source, int f){ vis[x][y] = 1; if(g[x][y] == 2){ vis[x][y] = 0; return; } if(g[x][y] != 1){ if(!con[source][trans(x, y)]) add_edge(source, trans(x, y)); vis[x][y] = 0; return; } if(g[x][y] == 1){ for(int i = 0; i < 8; i++){ int tx = x + dx[i]; int ty = y + dy[i]; if(tx >= 1 && tx <= m && ty >= 1 && ty <= n && trans(tx, ty) != source && trans(tx, ty) != f && !vis[tx][ty]) dfs(tx, ty, source, trans(x, y)); } } vis[x][y] = 0; } int dis[MAXN*MAXN]; LL cnt[MAXN*MAXN]; bool inq[MAXN*MAXN]; void spfa(){ for(int i = 1; i <= n*m; i++) dis[i] = INF; queue<int> q; q.push(st); inq[st] = 1; dis[st] = 0; cnt[st] = 1; while(!q.empty()){ int cur = q.front(); q.pop(); inq[cur] = 0; for(int i = head[cur]; i; i = edge[i].nxt){ if(dis[edge[i].to] > dis[cur] + 1){ dis[edge[i].to] = dis[cur] + 1; cnt[edge[i].to] = cnt[cur]; if(!inq[edge[i].to]){ q.push(edge[i].to); inq[edge[i].to] = 1; } } else if(dis[edge[i].to] == dis[cur] + 1){ cnt[edge[i].to] += cnt[cur]; if(!inq[edge[i].to]){ q.push(edge[i].to); inq[edge[i].to] = 1; } } } } } int main(){ scanf("%d%d", &m, &n); for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++){ scanf("%d", &g[i][j]); if(g[i][j] == 3) st = trans(i, j); if(g[i][j] == 4) ed = trans(i, j); } for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ for(int k = 0; k < 8; k++){ int tx = i + dx[k]; int ty = j + dy[k]; if(tx >= 1 && tx <= m && ty >= 1 && ty <= n){ if(g[tx][ty] != 1 && g[tx][ty] != 2 && !con[trans(i, j)][trans(tx, ty)]) add_edge(trans(i, j), trans(tx, ty)); if(g[tx][ty] == 1) dfs(tx, ty, trans(i, j), trans(i, j)); } } } } spfa(); if(dis[ed] == INF){ printf("-1"); return 0; } printf("%d\n"outl, dis[ed]-1, cnt[ed]); return 0; }
- 1