0

私はこの問題を解決しようとしています：http：//olimpiada-informatica.org/ ？cmd = downloadE＆pbm = velo101＆ext = pdfスペイン語ですが、ここで翻訳しようと思います：

誰かが着陸帯でヴェロキラプトルを解放したことがわかったとき、あなたは地球に着陸しようとしています。
着陸旅行は長方形の形をしています。(.)空のスポット、Vヴェロキラプトル、障害物のあるスポットをドットでマークし#ます（着陸することはできません）。
ヴェロキラプトルが別の場所に行くのに1秒かかりますが、彼らは水平方向と垂直方向にしか移動できません。それらに着陸すると、残りの寿命を最大化するスポット
をマークするように求められます。X

ヴェロキラプトルのすべての位置を取得し、すべての位置でBFSを作成するアルゴリズムを実行しましたが、TLEを取得しています。コードは次のとおりです。

http://ideone.com/a6BVv3

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;

int cost[501][501],xx,yy,n,m;
char mat[501][501];
bool visit[501][501],first = true;

int a[] = {-1,0,0,1}, b[] = {0,-1,1,0};

void check(int x,int y,int level) {
  cost[x][y] = level;
  for(int i = 0; i < 4; ++i) {
    xx = x + a[i];
    yy = y + b[i];
    if(0 <= xx and xx < n and 0 <= yy and yy < m and mat[xx][yy] == '.') {
      if(!visit[xx][yy] or level + 1 < cost[xx][yy]) {
        visit[xx][yy] = true;
        check(xx,yy,level + 1);
      }
    }
  }
}

int max() {
  int r = -1;
  for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) if(mat[i][j] == '.') r = max(r,cost[i][j]);
  return r;
}

void show() {
  if(!first) puts("---");
  int r = max();
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < m; ++j) {
      if(cost[i][j] == r) printf("X");
      else printf("%c",mat[i][j]);
    }
    puts("");
  }
}

int main() {
  while(scanf("%d %d",&n,&m) == 2) {
    queue<pair<int,int> > cola;
    for(int i = 0; i < n; ++i) {
      scanf("\n");
      for(int j = 0; j < m; ++j) {
        scanf("%c",&mat[i][j]);
        if(mat[i][j] == 'V') cola.push(make_pair(i,j));
      }
    }
    memset(cost,-1,sizeof cost);
    memset(visit,0,sizeof visit);
    while(!cola.empty()) {
      pair<int,int> aux = cola.front();
      visit[aux.first][aux.second] = true;
      check(aux.first, aux.second,0);
      cola.pop();
    }
    show();
    first = false;
  }
  return 0;
}

アルゴリズムを改善する方法を知っている人はいますか？

編集

わかりました、私は問題を解決することができました、誰かが興味を持っているならここにコードがあります：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;

int cost[501][501],n,m;
char mat[501][501];
bool visit[501][501],first = true;
queue<pair<int,int> > cola;

int a[] = {-1,0,0,1}, b[] = {0,-1,1,0};

int max() {
  int r = -1;
  for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) if(mat[i][j] == '.') r = max(r,cost[i][j]);
  return r;
}

void show() {
  if(!first) puts("---");
  int r = max();
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < m; ++j) {
      if(cost[i][j] == r) printf("X");
      else printf("%c",mat[i][j]);
    }
    puts("");
  }
}

int main() {
  int cont = 0,x,y,xx,yy,level;
  while(scanf("%d %d",&n,&m) == 2) {
    for(int i = 0; i < n; ++i) {
      scanf("\n");
      for(int j = 0; j < m; ++j) {
        scanf("%c",&mat[i][j]);
        if(mat[i][j] == 'V') cola.push(make_pair(i,j));
      }
    }
    memset(cost,-1,sizeof cost);
    memset(visit,0,sizeof visit);
    while(!cola.empty()) {
      int s_cola = cola.size();
      for(int i = 0; i < s_cola; ++i) {
        x = cola.front().first, y = cola.front().second;
        cola.pop();
        level = cost[x][y];
        for(int i = 0; i < 4; ++i) {
          xx = x + a[i], yy = y + b[i];
          if(0 <= xx and xx < n and 0 <= yy and yy < m and mat[xx][yy] == '.') {
            if(!visit[xx][yy] or level + 1 < cost[xx][yy]) {
              visit[xx][yy] = true;
              cost[xx][yy] = level + 1;
              cola.push(make_pair(xx,yy));
            }
          }
        }
      }
    }
    show();
    first = false;
  }
  return 0;
}
4

1 に答える 1

1

check() でグラフ全体の深さ優先検索を行っています。深さ優先で最短パスを見つけようとする代わりに、それを main() のループと統合します。

于 2012-11-29T01:55:53.107 に答える