久久亚洲中文字幕精品一区四,天天综合久久久网,奇米影视7777久久精品

poj 1101

//======================================

這道題大多數人都用的是廣搜+優先隊列，不過我的做法是深搜

做起來還不是很繁瑣，不過最讓人詫異的就是我原來把數組開到了

77 ，因為w,h最大值是75加上兩行外圍空地，最大開到77就可以了啊

但是結果卻是一直WA，困擾我很長時間，后來改到數組開到了100

ok ac

.，覺得很怪異，然后把數組開到78還是可以ac的，發出來

供路過的acmer指點迷津。。。

//======================================

#include <iostream>
#include <string>
#define MAXN 78
#define min _min
#define inf 123456789
using namespace std;

char _m[MAXN][MAXN];
bool mark[MAXN][MAXN];
int dp[MAXN][MAXN];
int dis[4][2] = {0,1,0,-1,1,0,-1,0};
int dis_mark[4] = {4,3,2,1};
int min;
int x_2;
int y_2;
int real_w;
int real_h;
void dfs(int x,int y,int dir,int step);
int main()
{
freopen("acm.acm","r",stdin);
// freopen("out.txt","w",stdout);
int w;
int h;
int i;
int j;
int x_1;
int y_1;
int temp_x;
int temp_y;
string s;
int time = 0;
while(cin>>w>>h,w||h)
{
   cout<<"Board #"<<++ time<<":"<<endl;
   getchar();
   int time_in = 0;
   real_w = w+2;
   real_h = h+2;
   memset(_m,' ',sizeof(_m));
   for(i = 1; i <= h; ++ i)
   {
    getline(cin,s);
    for(j = 1; j <= w; ++ j)
    {
     _m[i][j] = s[j-1];
    }
   }


   while(cin>>y_1>>x_1>>y_2>>x_2,x_1||y_1||x_2||y_2)
   {

    cout<<"Pair "<<++ time_in<<": ";
    memset(mark,false,sizeof(mark));
    for(i = 0; i < MAXN; ++ i)
    {
     for(j = 0; j < MAXN; ++ j)
     {
      dp[i][j] = inf;
     }
    }
    min = inf;
    for(i = 0; i < 4; ++ i)
    {
     temp_x = x_1 + dis[i][0];
     temp_y = y_1 + dis[i][1];
     if((_m[temp_x][temp_y] != 'X' ||_m[temp_x][temp_y] == 'X' && temp_x == x_2 && temp_y == y_2) && !mark[temp_x][temp_y])
     {
      mark[temp_x][temp_y] = true;
      dfs(temp_x,temp_y,dis_mark[i],1);

      mark[temp_x][temp_y] = false;
     }
    }
    if(min == inf)
    {
     cout<<"impossible."<<endl;
    }
    else
    {
     cout<<min;
     cout<<" segments."<<endl;
    }
   }
   cout<<endl;
}
}

void dfs(int x,int y,int dir,int step)
{
if(x == x_2 && y == y_2)
{
   if(step < min)
   {
    min = step;
   }
   return;
}

if(step < dp[x][y])
{
   dp[x][y] = step;
}
else
{
   return;
}

int i;
int j;
int temp_x;
int temp_y;// 右
for(i = 0; i < 4; ++ i)
{
   temp_x = dis[i][0] + x;
   temp_y = dis[i][1] + y;
   if(temp_x >= 0 && temp_x < real_h && temp_y >= 0 && temp_y <= real_w &&( _m[temp_x][temp_y] != 'X' || _m[temp_x][temp_y] == 'X' && temp_x == x_2 && temp_y == y_2)&& !mark[temp_x][temp_y])
   {
    mark[temp_x][temp_y] = true;
    if(dis_mark[i] != dir)
    {
     dfs(temp_x,temp_y,dis_mark[i],step+1);
     if(step+1 < dp[temp_x][temp_y])
      dp[temp_x][temp_y] = step+1;
    }
    else
    {
     dfs(temp_x,temp_y,dis_mark[i],step);
     if(step < dp[temp_x][temp_y])
      dp[temp_x][temp_y] = step;
    }
    mark[temp_x][temp_y] = false;
   }
}

}

posted on 2010-06-19 17:00 成大才子閱讀(696) 評論(2) 編輯收藏引用

# re: poj 1101 2010-09-14 15:43 rayafjyblue

# re: poj 1101 2010-09-25 09:08 caizi

poj 1101

評論

導航

統計

公告

常用鏈接

留言簿(1)

隨筆檔案

文章分類

文章檔案

鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理