臨近畢業真是各種瑣事多，好不容易寫完幾萬字蛋疼的論文，又接著戶口檔案掛靠，畢業旅游，20多個離校蓋章，簽證被check了幾個星期還沒消息，希望8月初能走啊。
各種事情之下，人就是懶加心散，好久沒寫代碼，也時間寫，再說也不知道寫啥。突然心血來潮還是刷刷題，不然都忘記代碼怎麼寫了。
Poj33222，Bloxorz，一個很有意思的小游戲，一道中等的搜索題目。該題目也是相關游戲的AI算法的一個典型思路：利用BFS或者DFS來不斷搜索下一步所有可能的游戲狀態，繼而找到解（像推箱子都可以用類似思路解決），為了加速可以利用剪枝，常量表等技巧。不過不知道為啥一開始用Java沒過，後來無奈，語法稍微改成C++就過了。。POJ的神奇。。
#include <iostream>
#include<algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
//------>y
//|
//|
//|
//x
class Node
{
public:
int lx,ly;
bool stand;
bool horizontal;
int t;
Node()
{
}
Node(int x,int y,bool s,bool h, int t)
{
this->lx = x;
this->ly = y;
this->stand = s;
this->horizontal = h;
this->t = t;
}
};
char map[501][501];
int visMat[502][502][3] ;//0:stand 1:horizontal 2:vertical
const int MAX = 1<<30;
bool TestLie(int lx, int ly, bool hFlag, int r, int c)
{
if(lx<0 || lx >=r || ly<0 || ly>=c)
{
return false;
}
if(hFlag == true)
{
if(ly < c-1)
{
if( (map[lx][ly] != '#') && (map[lx][ly+1] != '#') )
return true;
}
}
else//lie vertically
{
if(lx < r-1)
{
if( (map[lx][ly] != '#') && (map[lx+1][ly] != '#') )
return true;
}
}
return false;
}
bool TestStand(int lx, int ly, int r, int c)
{
if(lx>=0 && ly>=0 && lx < r && ly < c && map[lx][ly]!='#' && map[lx][ly]!='E')
return true;
return false;
}
int BFSearch(int r,int c,Node sNode, int ex,int ey)
{
int visNum = -1;
queue<Node> nodeQueue;
nodeQueue.push(sNode);
while(nodeQueue.empty() == false)
{
Node node = nodeQueue.front();
nodeQueue.pop();
/////////////////Test if it meets the end/////////////////////////
if(node.stand == true && node.lx == ex && node.ly == ey)
{
//Find the solution.
visNum = visMat[node.lx][node.ly][0];
break;
}
//System.out.println(node.lx+" "+node.ly+" "+node.stand+" "+node.horizontal+" "+node.t);
//////////////////////////////////////////////////////////////////
if(node.stand == true)//stand
{
//lie vertical up
if(TestLie((node.lx - 2), node.ly, false, r, c)
&&
node.t + 1 < visMat[node.lx-2][node.ly][2])
{
Node tNode((node.lx-2), node.ly, false, false, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx-2][node.ly][2] = node.t + 1;
}
//lie vertical down
if(TestLie((node.lx + 1), node.ly, false, r, c)
&&
node.t + 1 < visMat[node.lx+1][node.ly][2])
{
Node tNode((node.lx+1), node.ly, false, false, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx+1][node.ly][2] = node.t + 1;
}
//lie horizontal left
if(TestLie(node.lx, (node.ly - 2), true, r, c)
&&
node.t + 1 < visMat[node.lx][node.ly - 2][1])
{
Node tNode(node.lx, (node.ly - 2), false, true, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx][node.ly - 2][1] = node.t + 1;
}
//lie horizontal right
if(TestLie(node.lx, (node.ly + 1), true, r, c)
&&
node.t + 1 < visMat[node.lx][node.ly + 1][1])
{
Node tNode(node.lx, (node.ly + 1), false, true, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx][node.ly + 1][1] = node.t + 1;
}
}
else//lie
{
if(node.horizontal == true)
{
//lie horizontal towards up
if(TestLie((node.lx - 1 ), node.ly, true, r, c)
&&
node.t + 1 < visMat[node.lx-1][node.ly][1])
{
Node tNode((node.lx-1), node.ly, false, true, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx-1][node.ly][1] = node.t + 1;
}
//lie horizontal towards down
if(TestLie((node.lx + 1 ), node.ly, true, r, c)
&&
node.t + 1 < visMat[node.lx+1][node.ly][1])
{
Node tNode((node.lx+1), node.ly, false, true, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx+1][node.ly][1] = node.t + 1;
}
//stand towards left
if(TestStand(node.lx, (node.ly-1), r, c)
&&
node.t + 1 < visMat[node.lx][node.ly-1][0])
{
Node tNode(node.lx, (node.ly-1), true, false, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx][node.ly - 1][0] = node.t + 1;
}
//stand towards right
if(TestStand(node.lx, (node.ly+2), r, c)
&&
node.t + 1 < visMat[node.lx][node.ly+2][0])
{
Node tNode(node.lx, (node.ly+2), true, false, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx][node.ly + 2][0] = node.t + 1;
}
}
else//lie vertically at first
{
//lie vertically towards left
if(TestLie(node.lx, (node.ly-1), false, r, c)
&&
node.t + 1 < visMat[node.lx][node.ly-1][2])
{
Node tNode(node.lx, (node.ly-1), false, false, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx][node.ly-1][2] = node.t + 1;
}
//lie vertically toward right
if(TestLie(node.lx, (node.ly+1), false, r, c)
&&
node.t + 1 < visMat[node.lx][node.ly+1][2])
{
Node tNode(node.lx, (node.ly+1), false, false, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx][node.ly+1][2] = node.t + 1;
}
//stand towards up
if(TestStand( (node.lx-1), node.ly, r, c)
&&
node.t + 1 < visMat[node.lx-1][node.ly][0])
{
Node tNode((node.lx-1), node.ly, true, false, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx-1][node.ly][0] = node.t + 1;
}
//stand towards down
if(TestStand((node.lx+2), node.ly, r, c)
&&
node.t + 1 < visMat[node.lx+2][node.ly][0])
{
Node tNode((node.lx+2), node.ly, true, false, (node.t+1));
nodeQueue.push(tNode);
visMat[node.lx+2][node.ly][0] = node.t + 1;
}
}
}
}
return visNum;
}
int main()
{
int r,c;
scanf("%d%d",&r,&c);
while(r!=0 && c!=0)
{
int ex = 0,ey = 0;
Node sNode;
sNode.t = 0;
//Initialize the map
for(int i=0;i<r;i++)
{
scanf("%s",map[i]);
}
//for(int i=0;i<r;i++)
//{
// for(int j=0;j<c;j++)
// {
// cout<<map[i][j];
// }
// cout<<endl;
//}
//Find the start point and end point.
int flag = 0;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if( (map[i][j] == 'X') && ((flag & 1) == 0) )
{
flag = flag | 1;
if( (j+1 < c) && (map[i][j+1] == 'X') )
{
sNode.horizontal =true;
sNode.stand = false;
sNode.lx = i;
sNode.ly = j;
visMat[i][j][1] = 0;
}
else if( (i+1<r) && (map[i+1][j] == 'X') )
{
sNode.horizontal =false;
sNode.stand = false;
sNode.lx = i;
sNode.ly = j;
visMat[i][j][2] = 0;
}
else
{
sNode.stand = true;
sNode.lx = i;
sNode.ly = j;
visMat[i][j][0] = 0;
}
}
else if(map[i][j] == 'O')
{
flag = flag | (1<<1);
ex = i;
ey = j;
}
}
if(flag == 3)
break;
}
////Initialize the visit matrix
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
for(int k=0;k<3;k++)
{
visMat[i][j][k] = MAX;
}
//memset(visMat,MAX,sizeof(visMat));
int step = BFSearch(r, c, sNode, ex,ey);
if(step >= 0)
{
printf("%d\n",step);
}
else
{
printf("Impossible\n");
}
scanf("%d%d",&r,&c);
}
}
