0
Your rating: None

CodeChef submission 61897 (C++ 4.0.0-8)

CodeChef submission 61897 (C++ 4.0.0-8) plaintext list. Status: AC, problem B1, contest . By triplem (Stephen Merriman), 2009-08-01 05:49:04.
  1. #include <iostream>
  2. #include <list>
  3. #include <queue>
  4. using namespace std;
  5. char grid[1000][1001];
  6. int dist[1000][1000];
  7. int delta[8][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
  8. list<int> ds;
  9. typedef struct State {
  10.     int x, y, val;
  11.     bool seen;
  12.     bool operator<(const State& s) const {
  13.         return val<s.val;
  14.     }
  15. };
  16. priority_queue<State> pq;
  17. State states[1000][1000];
  18. int main() {
  19.     int N,M; scanf("%d %d",&N,&M);
  20.     int sx,sy,ex,ey;
  21.     for (int i=0; i<N; i++) {
  22.         scanf("%s",grid[i]);
  23.         for (int j=0; j<M; j++) {
  24.             states[i][j].x=i;
  25.             states[i][j].y=j;
  26.             states[i][j].val=10000;
  27.             states[i][j].seen=false;
  28.             if (grid[i][j]=='@') {
  29.                 sx=i;sy=j;grid[i][j]='.';
  30.             } else if (grid[i][j]=='$') {
  31.                 ex=i;ey=j;grid[i][j]='.';
  32.             } else if (grid[i][j]=='D') {
  33.                 ds.push_back(i*M+j);
  34.                 states[i][j].val=0;
  35.             }
  36.         }
  37.     }
  38.     int score = 0;
  39.     while (true) {
  40.         score++;        
  41.         int sz = ds.size();
  42.         if (sz==0) break;
  43.         for (int i=0; i<sz; i++) {
  44.             int next = ds.front();
  45.             int x = next/M;
  46.             int y = next%M;
  47.             ds.pop_front();
  48.             for (int j=0; j<8; j++) {
  49.                 int xx = x + delta[j][0];
  50.                 int yy = y + delta[j][1];
  51.                 if (xx>=0 && yy>=0 && xx<N && yy<M && states[xx][yy].val==10000) {
  52.                     states[xx][yy].val=score;
  53.                     ds.push_back(xx*M+yy);
  54.                 }
  55.             }
  56.         }
  57.     }
  58.     pq.push(states[sx][sy]);
  59.     states[sx][sy].seen=true;
  60.     int curans = 10000;
  61.     
  62.     while (true) {
  63.         State next = pq.top();
  64.         pq.pop();
  65.         curans<?=next.val;
  66.         if (next.x==ex && next.y==ey) break;
  67.         for (int i=0; i<8; i++) {
  68.             int xx = next.x + delta[i][0];
  69.             int yy = next.y + delta[i][1];
  70.             if (xx>=0 && yy>=0 && xx<N && yy<N && !states[xx][yy].seen) {
  71.                 states[xx][yy].seen=true;
  72.                 pq.push(states[xx][yy]);
  73.             }
  74.         }
  75.     }
  76.     printf("%d\n",curans);
  77. }
  78.

Comments