Deskripsi masalah:

enter image description here

Saya mencoba memecahkan masalah di internet dan saya tidak dapat melewati semua kasus uji, karena logika saya cacat dan salah. Kekurangannya: Saya berasumsi mulai dari titik 'F' terdekat akan selalu membawa saya ke jalur terpendek, di semua kasus.

Pikir saya memikirkan:

  • Mengubah ini menjadi masalah grafik dan menyelesaikannya berdasarkan itu. > tidak berpikir ini akan berhasil karena kendala?
  • Cobalah untuk mendapatkan semua kemungkinan kombinasi solusi > tidak berskala, jika kombinasi !8 ada.
#include <iostream>
#include <utility> 
#include <string>
#include <vector>
#include <queue>
using namespace std;

#define N 4
#define M 4

int SearchingChallenge(string strArr[], int arrLength) {
  int  n = arrLength, m = n, steps = 0, food = 0;
  // initial position of charlie
  int init_j = 0;
  int init_i = 0;
  queue<pair<int,int>> q;
  // directions
  vector<int> offsets = {0,-1,0,1,0};
  vector<pair<int,int>> food_nodes;
  //store visited nodes, no need for extra work to be done.
  int visited_nodes[4][4] = {{0}};
  
  // get number of food pieces 
  for(int i = 0; i < m; i++){
    for(int j = 0; j < n ; j++){
      if(strArr[i][j] == 'F')
      {
          food++;
      }
      if(strArr[i][j] == 'C')
      {
        strArr[i][j] = 'O';
        food_nodes.push_back({i,j});
      }
    }
  }
  while(food_nodes.size()>0){
      food_nodes.erase(food_nodes.begin());
      int break_flag=0;
      q.push(food_nodes[0]);
  while(!q.empty()){
      int size = q.size();
      while(size-->0){
      pair<int,int> p = q.front();
      q.pop();
      for(int k = 0; k < 4; k++){
      int ii = p.first + offsets[k], jj = p.second + offsets[k+1];
    /*  if(ii == 0 && jj == 3)
        printf("HI"); */
      if(jj >= 0 && jj < 4 && ii < 4 && ii >=0){
          if(strArr[ii][jj] == 'F'){
             strArr[ii][jj] = 'O';
            while(!q.empty())
                q.pop();
            break_flag=1;
            food--;
            food_nodes.push_back({ii,jj});
            break;
          }
          if(strArr[ii][jj] == 'O')
            q.push({ii,jj});
            
            
            if(strArr[ii][jj] == 'H' && food == 0)
                return ++steps;
        }   
     }
    if(break_flag==1)
        break;
    }
    steps++;
    if(break_flag==1)
        break;
  }
}
  return 0;
}

int main(void) { 
   
  // keep this function call here
  /* Note: In C++ you first have to initialize an array and set 
     it equal to the stdin to test your code with arrays. */

  //passing testcase
  //string A[4] = {"OOOO", "OOFF", "OCHO", "OFOO"};
  //failing testcase
  string A[4] = {"FOOF", "OCOO", "OOOH", "FOOO"}
  int arrLength = sizeof(A) / sizeof(*A);
  cout << SearchingChallenge(A, arrLength);
  return 0;
    
}

Bantuan Anda dihargai.

-1
haithamx15 7 Juli 2020, 02:31

1 menjawab

Jawaban Terbaik

Anda dapat menulis solusi DP di mana Anda memiliki kisi 4x4x8. Dua sumbu pertama mewakili koordinat x dan y. Yang ketiga mewakili pengkodean biner dari item makanan yang sudah Anda pilih.

Setiap sel di kotak menyimpan jumlah gerakan terbaik untuk dilakukan di sel ini setelah memakan makanan yang ditentukan. Jadi misalnya, grid[2][2][2] adalah biaya untuk sampai ke sel (2,2) setelah makan makanan kedua saja.

Kemudian Anda menetapkan nilai sel awal, pada indeks ketiga 0 hingga 0, semua sel lainnya menjadi -1. Anda menyimpan daftar sel yang akan disebarkan (diurutkan berdasarkan biaya terendah), dan Anda menambahkan sel awal ke dalamnya.

Kemudian Anda berulang kali mengambil sel berikutnya untuk menyebar, menghapusnya dan mendorong sel tetangga dengan biaya +1 dan memperbarui konsumsi makanan. Setelah Anda mencapai sel tujuan dengan semua makanan yang dikonsumsi, Anda selesai.

Itu seharusnya tidak lebih dari pembaruan 4x4x8, dengan urutan penyisipan antrian prioritas yang hampir sama. O(n log(n)) di mana n adalah xy2^f. Selama Anda memiliki sedikit makanan, ini akan hampir instan.

0
Jeffrey 7 Juli 2020, 01:11