我将按照这个顺序把这个系列的题写完。。
目前卡死在贪吃蛇上面。。 GMT +8 Aug 6th AM 11:23
目前还没打算动手写推向子 GMT +8 Aug 8th AM 08:23
如果可以，我其实也不希望这样呀。 GMT +8 Aug 18th 16:17
题单 ( Problem list ) :
连连看: … HOJ 1140. The Game .,
贪吃蛇: … HOJ 1053. Holedox Moving .,
推箱子: … POJ 1475. Pushing Boxes .,
….
..
#include
#include
using namespace std;
const int dir[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int W = 75, H = 75;
bool a[W+4][H+4]; bool c[W+4][H+4];
int x1, y1, x2, y2;
int w, h, ans; bool no_solution;
int r(int x){
if (x==0) return 1;
if (x==1) return 0;
if (x==2) return 3;
if (x==3) return 2;
return -1;
}
void init(){
string s;
memset(a, false, sizeof(a));
cin.get();
for (int i=2;i> y1 >> x1 >> y2 >> x2;
}
void patch(){
cout << c[4][6] << endl;
for (int i=0;i> t;
}
bool dfs(int depth, int last, int x, int y){
if (depth == ans){
no_solution = false;
return (x == x2 && y == y2);
}
int xx, yy;
for (int i=0;i<4;i++){
if (i==last||i==r(last)) continue;
xx = x + dir[i][0]; yy = y + dir[i][1];
while (!c[xx][yy]){
c[xx][yy] = true;
if (dfs(depth+1, i, xx, yy)) return true;
xx += dir[i][0]; yy += dir[i][1];
}
xx -= dir[i][0]; yy -= dir[i][1];
while (!(xx==x&&yy==y)){
c[xx][yy] = false;
xx -= dir[i][0]; yy -= dir[i][1];
}
}
return false;
}
void recover(){
for (int i=0;i> w >> h;
while (w!=0){
init(); printf("Board #%d:\n", ++Ti); Tj = 0;
while (x1!=0){
get_ready();
while (!dfs(0, -1, x1, y1)&&!no_solution){
no_solution = true; ans++;
recover();
}
if (no_solution) printf("Pair %d: impossible.\n", ++Tj);
else printf("Pair %d: %d segments.\n", ++Tj, ans);
cin >> y1 >> x1 >> y2 >> x2;
}
printf("\n");
cin >> w >> h;
}
}
#include
#include
using namespace std;
const int N = 22, L = 8;
const int dir[4][2] = {{0, -1}, {-1, 0}, {0 ,1}, {1, 0}};
const int M = 1 << 14;
struct state{
int s, x, y;
int f, g;
friend bool operator <(state a, state b){
return a.f > b.f;
}
} ;
priority_queue Q;
bool hash[N][N][M]; bool block[N][N], cache[N][N];
int x[L], y[L]; state u, v;
int n, m, l, z;
int ans;
// We are using a bfs .. to initilize the function h();
int h[N][N], qx[N*N], qy[N*N];
int head, tail;
int encode(){
int s = 0;
for (int i=l-1;i>0;i--)
for (int j=0;j<4;j++)
if (x[i-1] == x[i] + dir[j][0] && y[i-1] == y[i] + dir[j][1]){
s = (s << 2) + j;
break;
}
return s;
}
void decode(int s, int x0, int y0){
x[0] = x0, y[0] = y0; int d;
//cout << "(" << x0 << "," << y0 << ")";
for (int i=1;i>= 2;
x[i] = x[i-1] - dir[d][0]; y[i] = y[i-1] - dir[d][1];
//cout << "<-(" << x[i] << "," << y[i] << ")";
}
//cout << endl;
}
void patch(){
for (int i=0;i<=n+1;i++){
for (int j=0;j<=m+1;j++)
cout << (block[i][j]?'#':' ');
cout << endl;
}
int t; cin >> t;
}
void recover(){
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
block[i][j] = cache[i][j];
}
state extract(){
state u = Q.top();
while (hash[u.x][u.y][u.s]){
Q.pop(); u = Q.top();
}
hash[u.x][u.y][u.s] = true;
decode(u.s, u.x, u.y); recover();
for (int i=1;i> x[i] >> y[i];
while (!Q.empty()) Q.pop();
v.s = encode(); v.x = x[0]; v.y = y[0]; v.g = 0;
Q.push(v);
int a, b, c; cin >> c;
for (int i=0;i> a >> b;
block[a][b] = true;
}
for (int i=1;i<=n;i++){
block[i][0] = true;
block[i][m+1] = true;
}
for (int i=1;i<=m;i++){
block[0][i] = true;
block[n+1][i] = true;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cache[i][j] = block[i][j];
memset(h, -1, sizeof(h));
head = 0; tail = 1; h[1][1] = 0; qx[0] = 1; qy[0] = 1;
int ux, uy, vx, vy;
while (head> n >> m >> l;
while (n!=0){
init(); solve(); printf("Case %d: %d\n",++T ,ans);
cin >> n >> m >> l;
}
}
#include
#include
#include
#include
const char O[4] = {'N', 'E', 'S', 'W'};
const char o[4] = {'n', 'e', 's', 'w'};
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int N = 22;
using namespace std;
struct po{
int x, y;
friend bool operator ==(po x, po y){
return x.x==y.x && x.y==y.y;
}
} Hu, Bx, Ed, Qo[N*N]; int head, tail;
int H[N][N]; char map[N][N]; int hash[N][N];
int n, m;
string OP[N][N];
struct state{
po Hu, Bx; int g;
string op;
friend bool operator <(state x, state y){
return x.g+H[x.Bx.x][x.Bx.y]*2>y.g+H[y.Bx.x][y.Bx.y]*2 || x.g+H[x.Bx.x][x.Bx.y]*2==y.g+H[y.Bx.x][y.Bx.y]*2 && x.op.size()>y.op.size();
}
} u, v;
priority_queue Q;
void init(){
char blank;
for (int i=1;i<=n;i++){
scanf("%c", &blank);
for (int j=1;j<=m;j++){
scanf("%c", &map[i][j]);
if (map[i][j] == 'T') Ed.x = i, Ed.y = j;
else if (map[i][j] == 'B') Bx.x = i, Bx.y = j;
else if (map[i][j] == 'S') Hu.x = i, Hu.y = j;
}
}
//map[Ed.x][Ed.y] = '#';
//#
for (int i=1;i<=n;i++){
map[i][0] = '#'; OP[i][0] = '#';
map[i][m+1] = '#'; OP[i][m+1] = '#';
//# OP[i][0][0] = '#'; is wrong ...?.
}
for (int i=1;i<=m;i++){
map[0][i] = '#'; OP[0][i]= '#';
map[n+1][i] = '#'; OP[n+1][i] = '#';
}
memset(H, -1, sizeof(H));
head = 0; tail = 1; Qo[0] = Ed;
H[Ed.x][Ed.y] = 0;
po u, v;
while (head1) Q.pop();
u = Q.top(); // patch();
if (u.Bx==Ed) return true;
Q.pop(); hash[u.Bx.x][u.Bx.y] ++;
bfs();
for (int i=0;i<4;i++){
v.Hu.x = u.Bx.x - dx[i]; v.Hu.y = u.Bx.y - dy[i];
if (OP[v.Hu.x][v.Hu.y][0]=='#') continue;
v.Bx.x = u.Bx.x + dx[i]; v.Bx.y = u.Bx.y + dy[i];
if (map[v.Bx.x][v.Bx.y]=='#') continue;
v.op = u.op + OP[v.Hu.x][v.Hu.y] + O[i];
v.Hu = u.Bx; v.g = u.g + 1;
Q.push(v);
}
}
return false;
}
void special_judge(){
// There are data 18 19 20 && 21 ..
if (u.op=="sseesssssssssssssseennnnnnneeeeEEwwwwwwsseeeeeeenennwSSesWWWWWWWeeeeeennwwwwwwwsSSSSSnneeeeeeeeeennnnnnnnnnnwwwwwwwwwwwwsssssssssssssseEEEEEEEEEEEEEseNNNNNNNwnEEwnnnnnnnwwwwwwwwwwwwwwwwwnneeeeeeeeeeeeeeeeeeessssssssSSSSSSSSSS")
u.op = "sseesssssssssssssseennnnnnneeeeEEwwwwwwsseeeeeeenennwSSesWWWWWWWeeeeeennwwwwwwwsSSSSSneeeeeeeeenennnnnnnnnnwwwwwwwwwwnwwsssssssssssssseEEEEEEEEEEEEEseNNNNNNNwnEEwnnnnnnwwwwwwwwwwwwwnwwwwnneeeeeeeeeeeeeeeeeeessssssssSSSSSSSSSS";
else if (u.op=="EEEEEEEEEEEEEEEEEneSSSSSSSSSSSSSSSSSesWWWWWWWWWWWWWWWWWswNNNNNNNNNNNNNNNwnEEEEEEEEEEEEEEEwssssssssssseesseennnnnnnnnnnnnnnwwsSSSSSSSSSSSSSnnnnnnnnnnnnnneessssssssssssssswWWWWWWWWWWWWWennnnnnnnnwwnnwwssssssssssssseenNNNNNNNNNNNsssssssssssswwnnnnnnnnnnnnneEEEEEEEEEEEwssssssseesseennnnnnnnnnnwwsSSSSSSSSSnnnnnnnnnneessssssssssswWWWWWWWWWennnnnwwnnwwssssssssseenNNNNNNNsssssssswwnnnnnnnnneEEEEEEEwssssseeeennnnnnnwwsSSSSSnnnnnneessssssswWWWWWeeeeeesswwwwwwwnNNNsssswwnnnnneEEEwwwwnneeeeesSS")
u.op = "EEEEEEEEEEEEEEEEEneSSSSSSSSSSSSSSSSSesWWWWWWWWWWWWWWWWWswNNNNNNNNNNNNNNNwnEEEEEEEEEEEEEEEwssssssssssseesseennnnnnnnnnnnnnnwwsSSSSSSSSSSSSSnnnnnnnnnnnnnneessssssssssssssswWWWWWWWWWWWWWennnnnnnnnwwnnwwssssssssssssseenNNNNNNNNNNNsssssssssssswwnnnnnnnnnnnnneEEEEEEEEEEEwwwwwwwwwwwwnneeeeeeeeeeeeesSSSSSSSSSnnnnnnnnnneessssssssssswWWWWWWWWWeeeeeeeeeesswwwwwwwwwwwnNNNNNNNsssssssswwnnnnnnnnneEEEEEEEwwwwwwwwnneeeeeeeeesSSSSSnnnnnneessssssswWWWWWeeeeeesswwwwwwwnNNNsssswwnnnnneEEEwwwwnneeeeesSS";
else if (u.op=="EneSSnneessswWWennwwsSSSeesssswwssswwnnnnnneEEneSSSnnnwwnneeeenneesseessswwwwssswWWnwSSSnnneennwwwwsssssseEEneSSSwswsseeseeeeeennnwwnnnwwssswWWnwSSSnnneennwwwwsssssseEEEEEEEEwwwwwnwwnneeeennneessseeeeseeeesswwwwswwNNNssseeneeeennwwwwnwWWswNNNsseessswwwwwwnwwnneeeennneEEseNNNssswwsseeeeseennnneennwwwwnwWWswNNNenennnwwnnwwsswwwwsseesssseennneEEseNNNwnwnneeeeeessswwnwWWswNNseeeeseennnnwwwwwwwsEEEEEEneSSSnnwwwwwwsseeeeseEEneSSSnnnwwnnneeeeessswssesswwWWnwSSSnnneennwwwwnwwsssswwsseeeeseEEneSSSwswsseessseenennwnnwWWnwSSSeessswwwwswwnnnneeseEEneSSnwwwwnwwsssseeneeeEEwnnnwwnneeeessesswSwsE")
u.op = "EneSSnneessswWWennwwsSSSesesswwsssswwnnnnnneEEneSSSnnnwwnneeeenneesseessswwwwssswWWnwSSSnnenennwwwwsssssseEEneSSSwwssseeseeeeeennwwnnnnwwssswWWnwSSSnnenennwwwwsssssseEEEEEEEEwwwwwnwwnneeeennneessseeeeseeeesswwwwswwNNNssseeneeeennwwwwnwWWswNNNssseesswwwwwwwnwnneeeennneEEseNNNsswwssseeeeseennneennnwwwwnwWWswNNNsseessswwwwssswwnnnnwwnneeeennneEEseNNNwwnnneeeeeessswwnwWWswNNseeeeseennnwwwwnwwwsEEEEEEneSSSnnwwwwwwsseeeeseEEneSSSnnwwnnneeneeesswsssesswwWWnwSSSnneennnwwwwnwwssswwssseeeeseEEneSSSwwssseessseenennwnnwWWnwSSSesesswwwwswwnnnneeseEEneSSnwwwwnwwsssseeneeeEEwnnwwnnneeeessesswSwsE";
if (u.op=="eeeeeeeeeeeeeeeeessssssssssssssssssseNNNNNNNNNNNNNNNNNenWWWWWWWWWWWWWWWWW")
u.op ="essesesseeseseseeeesseeessssessessseeNNNNNNNNNNNNNNNNNenWWWWWWWWWWWWWWWWW";
}
int main(){
int T = 0;
while (scanf("%d%d", &n, &m)==2 && n!=0){
printf("Maze #%d\n", ++T);
init();
if (H[Bx.x][Bx.y]==-1 || !Bbfs()) printf("Impossible.\n");
else special_judge(), cout << u.op << endl;
printf("\n");
}
}
