UVa 12295 : Optimal Symmetric Paths

問題リンク : http://uva.onlinejudge.org/external/122/12295.html

問題概要 :
n * n のセルがあり、セルの中には1以上9以下の数字がかかれている
左上を(0,0), 右下を(n-1,n-1)としたとき、左上から右下へ移動する経路のうち、通ったセルの数字の和が最小となるようなものを数え上げろ
移動は上下左右の４方向である
ただし、経路は左したから右上にかけての対角線を基準として対称なものでなければならない
また、同じセルは一度しか訪れることができない

解法 :
dijkstra + DP で解いた
左上から対角線への最小コストをdijkstraで求める
移動先と対称なセルの数字も一緒に足してしまいながらdijkstraすること
左上から対角線までの各セルについて、移動コストが小さい順でソートする
移動コストが同じ場合はマンハッタン距離が小さい順でソートする
dpという名前の2次元配列を用意し、dp[0][0] = 1、その他は0で初期化する
先ほどソートした順にセルを見ていき、上下左右をみて(今いる場所の最短コスト)+(移動することでかかるコスト) == (行き先の最短コスト) となっているような場所にdpの今いる場所の値を加算する
あとは対角線上似合って移動コストが最短のもののdpを足し合わせれば良い

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const ll MOD = 1000000009LL;

struct Data{
  int x,y,weight,manhattan;
  bool operator < ( const Data &data ) const {
    if( weight != data.weight ) return weight < data.weight;
    if( manhattan != data.manhattan ) return manhattan < data.manhattan;
    return ( x != data.x ) ? x < data.x : y < data.y;
  }
};

struct Node{
  int x,y,weight;
  bool operator < ( const Node &node ) const {
    if( weight != node.weight ) return weight > node.weight;
    return ( x != node.x ) ? x > node.x : y > node.y;
  }
};

int n,cost[110][110],mindist[110][110];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
ll dp[110][110];

bool isValid(int x,int y) { return 0 <= x && x < n && 0 <= y && y < n; }

void compute(){
  rep(i,n) rep(j,n) mindist[i][j] = IINF;
  mindist[0][0] = cost[0][0] + cost[n-1][n-1];
  priority_queue<Node> Q;
  Q.push((Node){0,0,cost[0][0]+cost[n-1][n-1]});
  while( !Q.empty() ){
    Node node = Q.top(); Q.pop();
    if( mindist[node.y][node.x] < node.weight ) continue;
    rep(i,4){
      int nx = node.x + dx[i], ny = node.y + dy[i];
      if( !isValid(nx,ny) ) continue;
      int ncost = node.weight + ( ( ny == n-1-nx && nx == n-1-ny ) ? cost[ny][nx] : cost[ny][nx] + cost[n-1-nx][n-1-ny]);
      if( mindist[ny][nx] > ncost ) {
        mindist[ny][nx] = ncost;
        Q.push((Node){nx,ny,mindist[ny][nx]});
      }
    }
  }

  vector<Data> order;
  rep(i,n) rep(j,n-i) order.push_back((Data){j,i,mindist[i][j],i+j});
  sort(order.begin(),order.end());
  
  rep(i,n) rep(j,n) dp[i][j] = 0;
  dp[0][0] = 1LL;
  rep(i,order.size()) {
    int x = order[i].x, y = order[i].y;
    rep(j,4) {
      int nx = x + dx[j], ny = y + dy[j];
      if( !isValid(nx,ny) ) continue;
      int ncost = mindist[y][x] + ( ( nx == n-1-ny && ny == n-1-nx ) ? cost[ny][nx] : cost[ny][nx] + cost[n-1-nx][n-1-ny]);
      if( ncost != mindist[ny][nx] ) continue;
      ( dp[ny][nx] += dp[y][x] ) %= MOD;
    }
  }

  int mini = IINF;
  rep(i,n) mini = min(mini,mindist[i][n-i-1]);
  ll sum = 0;
  rep(i,n) if( mini == mindist[i][n-i-1] ) ( sum += dp[i][n-i-1] ) %= MOD;
  cout << sum << endl;
}

int main(){
  while( cin >> n, n ){
    rep(i,n) rep(j,n) cin >> cost[i][j];
    compute();
  }
  return 0;
}

他の人の解法をみてみるとdijkstraの最中に数え上げてた
普通にそれで良いではないか。
dijkstraで同時に数え上げるコードは以下の通り

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const ll MOD = 1000000009LL;

struct Data{
  int x,y,weight,manhattan;
  bool operator < ( const Data &data ) const {
    if( weight != data.weight ) return weight < data.weight;
    if( manhattan != data.manhattan ) return manhattan < data.manhattan;
    return ( x != data.x ) ? x < data.x : y < data.y;
  }
};

struct Node{
  int x,y,weight;
  bool operator < ( const Node &node ) const {
    if( weight != node.weight ) return weight > node.weight;
    return ( x != node.x ) ? x > node.x : y > node.y;
  }
};

int n,cost[110][110],mindist[110][110];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
ll dp[110][110];

bool isValid(int x,int y) { return 0 <= x && x < n && 0 <= y && y < n; }

void compute(){
  rep(i,n) rep(j,n) mindist[i][j] = IINF, dp[i][j] = 0;
  dp[0][0] = 1LL;
  mindist[0][0] = cost[0][0] + cost[n-1][n-1];
  priority_queue<Node> Q;
  Q.push((Node){0,0,cost[0][0]+cost[n-1][n-1]});
  while( !Q.empty() ){
    Node node = Q.top(); Q.pop();
    if( mindist[node.y][node.x] < node.weight ) continue;
    rep(i,4){
      int nx = node.x + dx[i], ny = node.y + dy[i];
      if( !isValid(nx,ny) ) continue;
      if( nx > n-1-ny ) continue;
      int ncost = node.weight + ( ( nx == n-1-ny && ny == n-1-nx ) ? cost[ny][nx] : cost[ny][nx] + cost[n-1-nx][n-1-ny]);
      if( mindist[ny][nx] > ncost ) {
        mindist[ny][nx] = ncost;
        dp[ny][nx] = dp[node.y][node.x];
        Q.push((Node){nx,ny,mindist[ny][nx]});
      } else if( mindist[ny][nx] == ncost ) {
        ( dp[ny][nx] += dp[node.y][node.x] ) %= MOD;
      }
    }
  }
  int mini = IINF;
  rep(i,n) mini = min(mini,mindist[i][n-1-i]);
  ll sum = 0;
  rep(i,n) if( mindist[i][n-1-i] == mini ) ( sum += dp[i][n-1-i] ) %= MOD;
  cout << sum << endl;
}

int main(){
  while( cin >> n, n ){
    rep(i,n) rep(j,n) cin >> cost[i][j];
    compute();
  }
  return 0;
}