[TIOJ] 1013. Fire in the forest

題目連結:http://tioj.infor.org/problems/1013
其實我覺得題敘沒講清楚，火只會跟人一樣蔓延在可以走的地方....
先BFS個每個點會在第幾分鐘被火燒到，注意E是不會被燒到的，所以可以偷偷先把它改成不可通行(?，之後再BFS一次找最短路徑。 
#include <stdio.h>
#include <algorithm>
#include <queue>
#define INF 2147483647

using std::min;
using std::queue;

bool graph[10][17] = {
	{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
	{0,1,1,1,0,1,1,1,1,1,1,1,0,0,1,1,0},
	{0,0,1,1,0,1,1,1,1,0,1,0,1,0,1,1,0},
	{0,1,1,1,1,1,1,0,1,0,0,1,0,0,1,0,0},
	{0,1,1,0,0,1,1,1,0,0,1,1,0,0,1,0,0},
	{0,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,0},
	{0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0},
	{0,1,1,1,1,1,0,0,0,0,1,0,1,1,1,0,0},
	{0,0,0,0,1,0,1,0,1,1,1,1,1,1,1,1,0},
	{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
};

struct ff{
	int x,y,t;
};
struct mm{
	int x,y,t,v;
};

int tFire[10][17]={0};
int fX,fY;
int t;
int sX,sY, eX,eY;

int main(){
	scanf("%d%d%d%d%d%d%d",&fX,&fY,&t,&sX,&sY,&eX,&eY);
	graph[eX][eY]=0;
	queue<ff> q1;
	ff temp;
	temp.x=fX;
	temp.y=fY;
	temp.t=1;
	q1.push(temp);
	while(!q1.empty()){
		ff OAO = q1.front();
		q1.pop();
		tFire[OAO.x][OAO.y]=OAO.t;
		OAO.t++;
		if(OAO.x-1>=0 && graph[OAO.x-1][OAO.y] && tFire[OAO.x-1][OAO.y]==0){
			ff QAQ=OAO;
			QAQ.x--;
			q1.push(QAQ);
		}
		if(OAO.x+1<=9 && graph[OAO.x+1][OAO.y] && tFire[OAO.x+1][OAO.y]==0){
			ff QAQ=OAO;
			QAQ.x++;
			q1.push(QAQ);
		}
		if(OAO.y-1>=0 && graph[OAO.x][OAO.y-1] && tFire[OAO.x][OAO.y-1]==0){
			ff QAQ=OAO;
			QAQ.y--;
			q1.push(QAQ);
		}
		if(OAO.y+1<=16 && graph[OAO.x][OAO.y+1] && tFire[OAO.x][OAO.y+1]==0){
			ff QAQ=OAO;
			QAQ.y++;
			q1.push(QAQ);
		}
	}
	tFire[eX][eY]=INF;
	graph[eX][eY]=1;
	int r=INF;
	queue<mm> q2;
	mm tp;
	tp.x=sX;
	tp.y=sY;
	tp.t=t;
	tp.v=0;
	q2.push(tp);
	while(!q2.empty()){
		mm OAO = q2.front();
		q2.pop();
		if(tFire[OAO.x][OAO.y]<=OAO.t)continue;
		if(OAO.x==eX && OAO.y==eY) {r=min(r,OAO.v);break;}
		OAO.v++;
		OAO.t++;
		if(OAO.x-1>=0 && graph[OAO.x-1][OAO.y]){
			mm QAQ=OAO;
			QAQ.x--;
			q2.push(QAQ);
		}
		if(OAO.x+1<=9 && graph[OAO.x+1][OAO.y]){
			mm QAQ=OAO;
			QAQ.x++;
			q2.push(QAQ);
		}
		if(OAO.y-1>=0 && graph[OAO.x][OAO.y-1]){
			mm QAQ=OAO;
			QAQ.y--;
			q2.push(QAQ);
		}
		if(OAO.y+1<=16 && graph[OAO.x][OAO.y+1]){
			mm QAQ=OAO;
			QAQ.y++;
			q2.push(QAQ);
		}
	}
	if(r==INF)puts("Help!");
	else printf("%d",r);
	return 0;
}

留言

張貼留言

這個網誌中的熱門文章

[TIOJ] 1902. 「殿仁．王，不認識，誰啊？」，然後他就死了……

題目連結: https://tioj.infor.org/problems/1902 直接回滾莫隊後套個 trie 來查區間 xor 最大值，複雜度 $O((N^2/K + QK) \log C)$ 之類的(沒仔細算)，$K$好好挑一下就會過。 p.s. 好像好多古代人的解都是 $O(N^2 + Q)$ 😥 #include <algorithm> #include <functional> #include <iostream> #include <iterator> #include <numeric> #include <utility> #include <vector> int main() { std::cin.tie(nullptr)->sync_with_stdio(false); auto maxi = [](auto &a, auto b) { a = std::max(a, b); }; int n, q; std::cin >> n >> q; std::vector<uint32_t> a(1); std::copy_n(std::istream_iterator<int>(std::cin), n, std::back_inserter(a)); std::partial_sum(a.begin(), a.end(), a.begin(), std::bit_xor()); struct Q { int l, r, id; Q(int l_, int r_, int id_) : l(l_), r(r_), id(id_) {} }; static constexpr int K = 128; std::vector<std::vector<Q>> qs((n + K - 1) / K); for (int i = 0; i < q; ++i) { int l, r; std::cin >> l >> r; --l; qs[l / K
閱讀完整內容

[NPSC] 2009初賽 E. 檸檬汽水傳說

題目連結: http://contest.cc.ntu.edu.tw/npsc2009/2009sen.pdf 不 本題複雜度大概要做到$O(n)$或$O(n \log n)$，所以明顯naive的枚舉點對做法是不可能會好的，不妨思考其實每個人都只要往一邊看就好了，而且當看到一個比自己大的數就可以停了，那應該可用stack做，而明顯要用stack做的話，要有一定的單調性，想想後發現遞減的是好的，每次都pop掉比自己小的人並把pop了幾個加上去，不過值得注意的是如果是pop掉跟自己一樣的人的話，記得要把他原本的size記錄下來，之後要擺回去，因為其他人都還是可以跟你做匹配之類的，此外因為每個人都還可以跟隔壁的人溝通，所以當隔壁有人時記得多加一。 #include <bits/stdc++.h> using namespace std; class knight{ private: int __val; long long __size; public: knight(int a,int b){__val=a;__size=b;} int operator++(int a){if(a==0)return __size++;} bool operator<=(int a){return __val<=a;} bool operator==(int a){return __val==a;} friend void operator+=(long long &a, knight b){a+=b.__size;} }; stack<knight> ss; int main(){ int t; scanf("%d",&t); while(t--){ int sz; long long ans=0; scanf("%d",&sz); while(!ss.empty())ss.pop(); for(int i=0;i<sz;i++){ int aaa; scanf("%d",&aaa); long long kk=1; while(!ss.empty()&
閱讀完整內容

[AtCoder] [經典競程 90 題] 024 - Select +／- One（★2）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_x 題目大意: 給定兩個序列 $A$, $B$，每次操作可以把$A$中任意元素$A_i$變成$A_i-1$或$A_i+1$，問可不可以恰$K$次後把$A$變成$B$。 隨手用python寫了一個XD 總之想法就是如果$A_i$比$B_i$小，那我們一定至少要花$B_i-A_i$次把$A_i$變成$B_i$，比較大的 case 也差不多，於是我們就有了一個基礎的下界$\sum |A_i-B_i|$，如果$K$比這個下界少，那一定不可能可以讓$A$跟$B$一樣。而若超過這個下界的話，實際上我們也可以透過一連串的$+1$跟$-1$操作來刻意浪費那些多出來的步數，所以再多判一下奇偶性就可以知道是不是一定可以有解了。(奇偶性一樣就可以靠前面說的方式構造，不同的話則因為我們每一步對應的奇偶性都是固定的，所以不同則一定構不出來) n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) s = 0 for i in range(n): s += abs(a[i] - b[i]) print("Yes" if s <= k and s % 2 == k % 2 else "No")
閱讀完整內容