程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Topcoder SRM646 div1 600 bfs+剪枝

Topcoder SRM646 div1 600 bfs+剪枝

編輯:C++入門知識

Topcoder SRM646 div1 600 bfs+剪枝


因為只有47個blocks,所以現在小范圍內,即在-50 <= x <= 50,-50 <= y <= 50內進行bfs,之後盡量讓點向右走,記錄最大值。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker,"/STACK:1024000000");
#define EPS (1e-6)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 1000000007

using namespace std;

struct P
{
    int x,y,k;
};

queue

q; map,int> M; class TheGridDivOne { public : int find(vector x, vector y, int k) { q.push((P){0,0,0}); M.insert( pair,int> (pair(0,0),0)); P f,s; int i , n; n = x.size(); int Max = 0; map,int>::iterator it; while(q.empty() == false) { f = q.front(); q.pop(); if(k-f.k+f.x <= Max) continue; Max = max(Max,f.x); it = M.find(pair(f.x,f.y)); if(it->second < f.k) continue; int U = Mod,D = -Mod,L = -Mod,R = Mod; s = f; for(i = 0; i < n; ++i) { if(x[i] == s.x && y[i] > s.y) U = min(U,y[i]); if(x[i] == s.x && y[i] < s.y) D = max(D,y[i]); if(y[i] == s.y && x[i] > s.x) R = min(R,x[i]); if(y[i] == s.y && x[i] < s.x) L = max(L,x[i]); } s.y = f.y,s.x = min(f.x+k-f.k,R-1),s.k = f.k+s.x-f.x; it = M.find(pair(s.x,s.y)); if(it == M.end()) { q.push(s); M.insert( pair,int> (pair(s.x,s.y),s.k)); } else if(it->second > s.k) { q.push(s); it->second = s.k; } for(i = f.x-1; i > max(f.x-2,L); --i) { s.x = i,s.y = f.y,s.k = f.k + f.x-i; it = M.find( pair(s.x,s.y) ); if(s.k > k) break; if(it == M.end()) { M.insert( pair,int> (pair(s.x,s.y),s.k)); q.push(s); } else if(it->second > s.k) { it->second = s.k; q.push(s); } } for(i = f.y+1; i < min(f.y+2,U); ++i) { s.x = f.x,s.y = i,s.k = f.k + i-f.y; if(s.k > k) break; it = M.find( pair(s.x,s.y)); if(it == M.end()) { M.insert( pair,int> (pair(s.x,s.y),s.k)); q.push(s); } else if(it->second > s.k) { it->second = s.k; q.push(s); } } for(i = f.y-1; i > max(f.y-2,D); --i) { s.x = f.x,s.y = i,s.k = f.k + f.y-i; if(s.k > k) break; it = M.find( pair(s.x,s.y)); if(it == M.end()) { M.insert( pair,int> (pair(s.x,s.y),s.k)); q.push(s); } else if(it->second > s.k) { it->second = s.k; q.push(s); } } if(f.k <= 50) { for(i = f.x+1; i < min(f.x+2,R); ++i) { s.x = i,s.y = f.y,s.k = f.k + i-f.x; it = M.find( pair(s.x,s.y) ); if(s.k > k) break; if(it == M.end()) { M.insert( pair,int> (pair(s.x,s.y),s.k)); q.push(s); } else if(it->second > s.k) { it->second = s.k; q.push(s); } } } } return Max; } };



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved