NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2012國中組初賽
 B、勇者傳說

作者 主題: B、勇者傳說  (閱讀 1193 次)

darry140

  • 初級會員
  • **
  • 文章數: 32
    • 檢視個人資料
B、勇者傳說
« 於: 十一月 28, 2012, 06:19:47 pm »

這題只要用BFS就可以了
另外要計算起點到終點的距離所需的「補命寶丸」是否夠用
代碼: [選擇]
#include <iostream>
#include <cstring>
using namespace std;
struct que
{
int x,y;
};
int main()
{
int T;
cin>>T;
while (T--)
{
int side,blocks,HPplus;
cin>>side>>blocks>>HPplus;
int map[side][side];
memset(map,-1,sizeof(map));
int x,y;
for (int i=0;i<blocks;i++)
{
cin>>x>>y;
map[x][y]=-9;
}
if (map[0][0]==-9||map[side-1][side-1]==-9)
{
cout<<"-1\n";
continue;
}
map[0][0]=0;
bool visited[side][side];
memset(visited,false,sizeof(visited));
visited[0][0]=true;
struct que q[side*side];
int head=0,tail=1;
int dist[side][side];
memset(dist,-1,sizeof(dist));
dist[0][0]=0;
q[0].x=0;
q[0].y=0;
while (1)
{
if (q[head].x+1<side&&map[q[head].x+1][q[head].y]!=-9
    &&visited[q[head].x+1][q[head].y]==false)
    {
    q[tail].x=q[head].x+1;
q[tail].y=q[head].y;
visited[q[tail].x][q[tail].y]=true;
dist[q[tail].x][q[tail].y]=
dist[q[head].x][q[head].y]+1;
tail++;
    }
if (q[head].x-1>=0&&map[q[head].x-1][q[head].y]!=-9
    &&visited[q[head].x-1][q[head].y]==false)
    {
    q[tail].x=q[head].x-1;
q[tail].y=q[head].y;
visited[q[tail].x][q[tail].y]=true;
dist[q[tail].x][q[tail].y]=
dist[q[head].x][q[head].y]+1;
tail++;
    }
if (q[head].y+1<side&&map[q[head].x][q[head].y+1]!=-9
    &&visited[q[head].x][q[head].y+1]==false)
    {
    q[tail].x=q[head].x;
q[tail].y=q[head].y+1;
visited[q[tail].x][q[tail].y]=true;
dist[q[tail].x][q[tail].y]=
dist[q[head].x][q[head].y]+1;
tail++;
    }
if (q[head].y-1>=0&&map[q[head].x][q[head].y-1]!=-9
    &&visited[q[head].x][q[head].y-1]==false)
    {
    q[tail].x=q[head].x;
q[tail].y=q[head].y-1;
visited[q[tail].x][q[tail].y]=true;
dist[q[tail].x][q[tail].y]=
dist[q[head].x][q[head].y]+1;
tail++;
    }
head++;
if (head==tail)
break;
if (visited[side-1][side-1]==true)
break;
}
if (dist[side-1][side-1]>=100)
{
if (dist[side-1][side-1]/100>HPplus)
{
cout<<"-1\n";
continue;
}
else
{
cout<<dist[side-1][side-1]+dist[side-1][side-1]/100<<endl;
continue;
}
}
else
cout<<dist[side-1][side-1]<<endl;
}
return 0;
}
« 上次編輯: 十一月 28, 2012, 06:25:20 pm 由 darry140 »
記錄

WYJOIER

  • 新手
  • *
  • 文章數: 7
    • 檢視個人資料
Re: B、勇者傳說
« 回覆 #1 於: 四月 23, 2014, 05:16:27 pm »

附上我的解法~
代碼: [選擇]
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#define INF 2147483647
using namespace std;
int Map[101][101] , Record[101][101] , E[101][101];
struct Point{int x , y;};
inline int Readint()
{
char c = getchar();
while( !isdigit(c) )
c = getchar();
int Number = 0;
while( isdigit(c) )
Number = Number*10 + (c-'0') , c = getchar();
return Number;
}
void BFS( int N , int i , int j , int K , int Step )
{
queue<Point> Q;
Q.push( (Point){i,j} );
Record[i][j] = K , E[i][j] = 100;
if( Map[i][j] == INF )return;
Map[i][j] = Step;
while( !Q.empty() )
{
Point P = Q.front();
Q.pop();
if( E[P.x][P.y] == 0 )continue;
if( (E[P.x][P.y] == 1 && Record[P.x][P.y] > 0) && ( P.x < N-1 && P.x < N-1 ) )Record[P.x][P.y]-- , E[P.x][P.y] = 100 , Map[P.x][P.y]++;
if( (Map[P.x+1][P.y] != INF && P.x+1 < N) && (Map[P.x+1][P.y] == -1 || Map[P.x][P.y]+1 < Map[P.x+1][P.y]) )
{
Q.push( (Point){P.x+1,P.y} );
Map[P.x+1][P.y] = Map[P.x][P.y]+1;
E[P.x+1][P.y] = E[P.x][P.y]-1;
Record[P.x+1][P.y] = Record[P.x][P.y];
}
if( (Map[P.x][P.y+1] != INF && P.y+1 < N) && (Map[P.x][P.y+1] == -1 || Map[P.x][P.y]+1 < Map[P.x][P.y+1]) )
{
Q.push( (Point){P.x,P.y+1} );
Map[P.x][P.y+1] = Map[P.x][P.y]+1;
E[P.x][P.y+1] = E[P.x][P.y]-1;
Record[P.x][P.y+1] = Record[P.x][P.y];
}
if( (Map[P.x-1][P.y] != INF && P.x-1 >= 0) && (Map[P.x-1][P.y] == -1 || Map[P.x][P.y]+1 < Map[P.x-1][P.y]) )
{
Q.push( (Point){P.x-1,P.y} );
Map[P.x-1][P.y] = Map[P.x][P.y]+1;
E[P.x-1][P.y] = E[P.x][P.y]-1;
Record[P.x-1][P.y] = Record[P.x][P.y];
}
if( (Map[P.x][P.y-1] != INF && P.y-1 >= 0) && (Map[P.x][P.y-1] == -1 || Map[P.x][P.y]+1 < Map[P.x][P.y-1]) )
{
Q.push( (Point){P.x,P.y-1} );
Map[P.x][P.y-1] = Map[P.x][P.y]+1;
E[P.x][P.y-1] = E[P.x][P.y]-1;
Record[P.x][P.y-1] = Record[P.x][P.y];
}
}
return;
}
int main()
{
int T , N , M , K , x , y;
T = Readint();
while( T-- )
{
N = Readint();
M = Readint();
K = Readint();
memset( Map , -1 , sizeof(Map) );
while( M-- )
{
x = Readint();
y = Readint();
Map[x][y] = INF;
}
BFS( N , 0 , 0 , K , 0 );
printf("%d\n",Map[N-1][N-1] == INF ? -1 : Map[N-1][N-1]);
}
return 0;
}
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2012國中組初賽
 B、勇者傳說