題目連結
作法:
做BFS，紀錄每個點火與人分別要走幾步才能到達該點，
若火走 3 步到(i, j)，人需走4步才到(i, j)，
則該點人不能走，也就是不能加進BFS的queue。
須注意的點是:
1.人與火分開做BFS，即火全部BFS完後，再對人做BFS。
在另一篇前輩的文章說，同時做BFS會讓記憶體跳來跳去，可能造成TLE。
2.火不一定會擴散到整張地圖，
例如:
3 3
J..
###
F..
該點若火沒擴散到，人是可以走的(可以加進人的BFS qeuue中)。
**************************************************
程式碼:
/* 題目: UVa 11624 - Fire!
* Language: C++
* Created on: 2016年10月05日
* Author: hanting
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Coor
{
int i, j;
Coor(int a = 0, int b = 0)
{
i = a;
j = b;
}
};
int main()
{
int testCase;
cin >> testCase;
while(testCase--)
{
int r, c;
cin >> r >> c;
cin.get();
vector<vector<char> > vec(r+2, vector<char>(c+2, 0));
vector<vector<int> > fire(r+2, vector<int>(c+2, -1));
vector<vector<int> > joe(r+2, vector<int>(c+2, -1));
queue<Coor> J, F;
for(int i = 1; i <= r; i++)
{
for(int j = 1; j <= c; j++)
{
cin >> vec[i][j];
if(vec[i][j] == 'J')
{
joe[i][j] = 0;
J.push(Coor(i, j));
}
else if (vec[i][j] == 'F')
{
fire[i][j] = 0;
F.push(Coor(i, j));
}
}
}
Coor pos[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool escape = false;
int cnt = 0;
while(F.size())
{
Coor tmp = F.front();
F.pop();
int num = fire[tmp.i][tmp.j];
for(int i = 0; i < 4; i++)
{
int x, y;
x = tmp.i+pos[i].i;
y = tmp.j+pos[i].j;
if(fire[x][y]!=-1) continue;
if(vec[x][y] == '.'|| vec[x][y] == 'J')
{
F.push(Coor(x, y));
fire[x][y] = num+1;
}
}
}
while(J.size() && !escape)
{
Coor tmp = J.front();
J.pop();
int num = joe[tmp.i][tmp.j];
for(int i = 0; i < 4; i++)
{
int x, y;
x = tmp.i+pos[i].i;
y = tmp.j+pos[i].j;
if(vec[x][y] == 0)
{
escape = true;
cnt = num+1;
break;
}
if(joe[x][y]!=-1) continue;
if(vec[x][y] == '.' && (fire[x][y] == -1 || fire[x][y] > num+1))
{
J.push(Coor(x, y));
joe[x][y] = num+1;
}
}
}
if(escape)
{
cout << cnt << endl;
}
else
{
cout << "IMPOSSIBLE" << endl;
}
}
return 0;
}
2016年10月4日 星期二
[UVA] 11624 - Fire!
2016年10月2日 星期日
[UVA] 10181 - 15-Puzzle Problem
題目連結
TLE 幾百次後 才發現原因在 board[0][k] 居然不等於 board[k/4][k%4]，
改一下就AC了...害我一直對ida*優化到0秒
/* 題目: UVa 10181 - 15-Puzzle Problem
* Language: C++
* Created on: 2016年10月02日
* Author: hanting
*/
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
int board[4][4];
int table[16][2];
inline bool canSolve(int x)
{
int result = 0;
for(int i = 0; i < 16; i++)
{
for(int j = i+1; j < 16; j++)
{
if(board[j/4][j%4] and board[i/4][i%4] and board[j/4][j%4] < board[i/4][i%4]) result++;
}
}
return (result+x)&1;
}
inline int getStatus()
{
int cnt = 0;
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
if(board[i][j]) cnt += abs(table[board[i][j]][0] - i) + abs(table[board[i][j]][1] - j);
}
}
return cnt;
}
char ansStk[100];
char stk[100];
int stki;
enum
{
UP, DOWN, LEFT, RIGHT
};
int maxd;
int tmpMaxd;
int Htable[4][4][16]; // Htable[i][j][num] // num在[i][j]的cost
bool no;
bool dfs(int depth, int i, int j, int prePos, int status)
{
if(depth > 50)
{
no = true;
return false;
}
if(depth + status*4/3 > maxd)
{
tmpMaxd = min(tmpMaxd, depth + status*4/3);
if(depth == 0) maxd = tmpMaxd;
return false;
}
if(status == 0)
{
stk[stki] = 0;
cout << stk;
return true;
}
if(prePos != UP and i+1 < 4)
{
swap(board[i][j], board[i+1][j]);
stk[stki++] = 'D';
int nextStatus = status;
nextStatus -= Htable[i+1][j][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1 , i+1, j, DOWN, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i+1][j]);
}
if(prePos != LEFT and j+1 < 4)
{
swap(board[i][j], board[i][j+1]);
stk[stki++] = 'R';
int nextStatus = status;
nextStatus -= Htable[i][j+1][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1 , i, j+1, RIGHT, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i][j+1]);
}
if(prePos != DOWN and i-1 >= 0)
{
swap(board[i][j], board[i-1][j]);
stk[stki++] = 'U';
int nextStatus = status;
nextStatus -= Htable[i-1][j][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1, i-1, j, UP, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i-1][j]);
}
if(prePos != RIGHT and j-1 >= 0)
{
swap(board[i][j], board[i][j-1]);
stk[stki++] = 'L';
int nextStatus = status;
nextStatus -= Htable[i][j-1][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1 , i, j-1, LEFT, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i][j-1]);
}
maxd = tmpMaxd;
return false;
}
int main()
{
for(int i = 1; i < 16; i++)
{
table[i][0] = (i-1) / 4;
table[i][1] = (i-1) % 4 ;
}
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
for(int k = 1; k < 16; k++)
{
Htable[i][j][k] = abs(table[k][0] - i) + abs(table[k][1] -j);
}
}
}
int n;
cin >> n;
while(n--)
{
int x0, y0;
memset(ansStk, 0, sizeof(ansStk));
int ti = 0;
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
cin >> board[i][j];
if(board[i][j] == 0)
{
x0 = i;
y0 = j;
}
}
}
if(!canSolve(x0))
{
cout << "This puzzle is not solvable." << endl;
continue;
}
int status = getStatus();
maxd = status;
no = false;
for(;;)
{
tmpMaxd = 0x3fffffff;
stki = 0;;
if(dfs(0, x0, y0, -1, status))
{
break;
}
if(no)
{
cout << "This puzzle is not solvable." ;
break;
}
}
cout << endl;
}
return 0;
}
2016年7月12日 星期二
[UVA] 10428 - The Roots
題目連結
這題ac uva rank 1耶真是感動到快暴動了
程式碼:
/* 題目: UVa 10428 - The Roots
* Language: C++
* Created on: 2016年7月12日
* Author: hanting
*/
#include <iostream>
#include <cstring> // memset
#include <iomanip> // setprecision
#include <cmath> // fabs
#include <algorithm> // sort
#include <vector>
#include <cstdio>
using namespace std;
double a[6];
double f(double x) // 高效率求一元多次多項式的值
{
double result = a[5];
for(int i = 4; i >= 0; i--)
{
result = result * x + a[i];
}
return result;
}
double f1(double x)
{
double result = a[5]*5;
for(int i = 4; i > 0; i--)
{
result = result * x + a[i]*i;
}
return result;
}
double newtonsMethod(double x0)
{
double x1 = x0;
int cnt = 0;
do
{
if(++cnt == 100) break;
x0 = x1;
if(fabs(f(x0)) < 1e-10) return x0;
x1 = x0 - f(x0)/f1(x0);
}
while(fabs(x1 - x0) > 1e-10);
return x1;
}
void PolynomialDivision(double b, double c) // f div (bx+c)
{
for(int i = 5; i > 0; i--)
{
a[i-1] -= a[i] / b * c;
a[i] /= b;
}
for(int i = 0; i < 5; i++)
{
a[i] = a[i+1];
}
a[5] = 0;
}
void findRoot(vector<double> &root, int N)
{
double oneRoot;
while(root.size() < N)
{
oneRoot = newtonsMethod(0);
root.push_back(oneRoot);
PolynomialDivision(1, -oneRoot);
}
}
int main()
{
int N;
int caseN = 1;
while(/*cin >> N*/scanf("%d", &N) == 1 and N)
{
memset(a, 0, sizeof(a));
for(int i = N; i >= 0; i--)
{
//cin >> a[i];
scanf("%lf", a+i);
}
vector<double> root;
findRoot(root, N);
sort(root.begin(), root.end());
printf("Equation %d:", caseN++);
//cout << "Equation " << caseN++ << ":" ;
for(int i = 0; i < N; i++)
{
printf(" %.4lf", root[i]);
//cout << " " << fixed << setprecision(4) << root[i];
}
printf("\n");
//cout << endl;
}
return 0;
}2016年7月9日 星期六
[UVA] 684 - Integral Determinant
題目連結
程式碼:
/* 題目: UVa 684 - Integral Determinant
* Language: C++
* Created on: 2016年7月10日
* Author: hanting
*/
#include <iostream>
#include <vector>
using namespace std;
long long gcd(long long a1, long long b1)
{
unsigned long long a, b;
if(a1 < 0) a1 *= -1;
if(b1 < 0) b1 *= -1;
a = a1;
b = b1;
while(a and b)
{
(a > b) ? (a %= b) : (b %= a);
}
return a ? a : b;
}
long long lcm(long long a, long long b)
{
return a / gcd(a, b) * b; // a要先/gcd
}
struct Real
{
long long mom, son;
Real(int s = 0, int m = 1):mom(m), son(s) {}
void simple()
{
if(mom < 0)
{
son *= -1;
mom *= -1;
}
long long _gcd = gcd(mom, son);
mom /= _gcd;
son /= _gcd;
}
Real operator * (Real b)
{
Real result = *this;
long long gcd1, gcd2;
gcd1 = gcd(result.mom, b.son);
gcd2 = gcd(result.son, b.mom);
result.mom /= gcd1;
b.son /= gcd1;
result.son /= gcd2;
b.mom /= gcd2;
result.mom *= b.mom;
result.son *= b.son;
result.simple();
return result;
}
Real operator / (Real b)
{
Real result = *this;
long long gcd1, gcd2;
gcd1 = gcd(result.mom, b.mom);
gcd2 = gcd(result.son, b.son);
result.mom /= gcd1;
b.mom /= gcd1;
result.son /= gcd2;
b.son /= gcd2;
result.mom *= b.son;
result.son *= b.mom;
result.simple();
return result;
}
void operator -=(Real b)
{
long long lcm1 = lcm(mom, b.mom);
long long a1, b1;
a1 = lcm1 / mom;
b1 = lcm1 / b.mom;
son = son*a1 - b.son*b1;
mom = lcm1;
simple();
}
void operator *= (Real b)
{
long long gcdMom, gcdSon;
gcdMom = gcd(mom, b.son);
gcdSon = gcd(son, b.mom);
mom /= gcdMom;
b.son /= gcdMom;
son /= gcdSon;
b.mom /= gcdSon;
mom *= b.mom;
son *= b.son;
simple();
}
void operator /= (Real b)
{
long long gcd1, gcd2;
gcd1 = gcd(mom, b.mom);
gcd2 = gcd(son, b.son);
mom /= gcd1;
b.mom /= gcd1;
son /= gcd2;
b.son /= gcd2;
mom *= b.son;
son *= b.mom;
simple();
}
friend istream& operator >> (istream &in, Real &r)
{
in >> r.son;
r.mom = 1;
return in;
}
friend ostream& operator << (ostream &out, Real r)
{
out << r.son;
if(r.mom != 1 and r.son) out << '/' << r.mom;
return out;
}
};
void doDownTriangle(vector<vector<Real> > &vec) // 讓矩陣對角線以下全變為0
{
for(int k = 0; k < vec.size(); k++)
{
int index = k; // find first element not zero
while(index < vec.size() and vec[index][k].son == 0) index++;
if(index == vec.size())
{
vec[0][0] = 0;
return ;
}
if(index != k)
{
swap(vec[index], vec[k]);
for(int i = k; i < vec.size(); i++)
{
vec[k][i].son *= -1;
}
}
Real tmp = vec[k][k];
for(int i = k+1; i < vec.size(); i++)
{
Real r = vec[i][k] / tmp;
for(int j = k; j < vec[i].size(); j++)
{
vec[i][j] -= vec[k][j] * r;
}
}
}
}
Real Determinant(vector<vector<Real> > &vec)
{
doDownTriangle(vec);
Real result(1);
for(int i = 0; i < vec.size(); i++)
{
result *= vec[i][i]; // 因下三角全為0，故對角線乘積為答案
}
return result;
}
int main()
{
int n;
while(cin >> n and n)
{
vector<vector<Real> > matrix(n, vector<Real>(n));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
cin >> matrix[i][j];
}
cout <<Determinant(matrix) << endl;
}
cout << "*" << endl;
return 0;
}
2016年5月22日 星期日
[UVA] 11995 - I Can Guess the Data Structure!
/* 題目: UVa 11995 - I Can Guess the Data Structure!
* Language: C++
* Created on: 2016年5月22日
* Author: hanting
*/
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main()
{
int N;
while(cin >> N)
{
bool test[3] = {};
queue<int> que;
priority_queue<int> pque;
stack<int> stk;
int op;
int num;
for(int i = 0; i < N; i++)
{
cin >> op >> num;
if(op == 1)
{
que.push(num);
pque.push(num);
stk.push(num);
}
else //if(op == 2)
{
int tmp;
if(test[0] == 0)
{
if(que.size())
{
tmp = que.front();
if(tmp != num)
{
test[0] = 1;
}
else
{
que.pop();
}
}
else
{
test[0] = 1;
}
}
if(test[1] == 0)
{
if(pque.size())
{
tmp = pque.top();
if(tmp != num)
{
test[1] = 1;
}
else
{
pque.pop();
}
}
else
{
test[1] = 1;
}
}
if(test[2] == 0)
{
if(stk.size())
{
tmp = stk.top();
if(tmp != num)
{
test[2] = 1;
}
else
{
stk.pop();
}
}
else
{
test[2] = 1;
}
}
}
}
int cnt = 0;
for(int i = 0; i < 3; i++)
{
if(test[i] == 0) cnt++;
}
if(cnt == 0)
{
cout << "impossible" << endl;
}
else if(cnt == 1)
{
if(test[0] == 0)
{
cout << "queue" << endl;
}
else if(test[1] == 0)
{
cout << "priority queue" << endl;
}
else
{
cout << "stack" << endl;
}
}
else
{
cout << "not sure" << endl;
}
}
return 0;
}
2016年5月7日 星期六
[UVA] 11195 - Another n-Queen Problem
題目連結
==================================================
==================================================
程式碼:
/* 題目: UVa 11195 - Another n-Queen Problem
* Language: C++
* Created on: 2016年05月08日
* Author: hanting
*/
#include <iostream>
#include <vector>
#include <string>
#include <bitset>
using namespace std;
#pragma warning(disable:4996)
int ans;
vector<int > arr;
vector<string> vec;
void DFS(int row, int ld, int rd, int N, int cnt)
{
if (cnt == N)
{
ans++;
return;
}
int next = row | ld | rd;
for (int i = 0; i < N; i++)
{
int mask = 1 << i;
if (!(next & mask) && vec[cnt][i] != '*')
{
DFS(row|mask, (ld|mask) << 1, (rd|mask) >> 1, N, cnt + 1);
}
}
}
int main()
{
int N;
int CaseN = 1;
while (cin >> N && N)
{
ans = 0;
arr.assign(N, 0);
vec.assign(N, "");
for (int i = 0; i < N; i++)
{
cin >> vec[i];
}
DFS(arr[0], 0, 0, N, 0);
cout << "Case " << CaseN++ << ": " << ans << endl;
}
}
2016年5月1日 星期日
[UVA] 11956 - Brainfuck
/* 題目: UVa 11956 - Brainfuck
* Language: C++
* Created on: 2016年05月01日
* Author: hanting
*/
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
int CaseN = 1;
int testCase = 0;
cin >> testCase;
cin.get();
while(testCase--)
{
cout << dec << "Case " << CaseN++ << ":";
string ins;
getline(cin, ins);
unsigned char memory[100] = {};
int ptr = 0;
for(int i = 0; i < ins.size(); i++)
{
if(ins[i] == '+') memory[ptr]++;
else if(ins[i] == '-') memory[ptr]--;
else if(ins[i] == '>') ptr++;
else if(ins[i] == '<') ptr--;
if(ptr < 0) ptr = 99;
else if(ptr > 99) ptr = 0;
}
for(int i = 0; i < 100; i++)
{
cout << " ";
cout << setw(2);
cout << uppercase << setfill('0') << hex << (int)memory[i];
}
cout << endl;
}
return 0;
}
訂閱：
文章 (Atom)