NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2008國中組決賽
 C.喵喵抓老鼠

作者 主題: C.喵喵抓老鼠  (閱讀 2895 次)

wudaiyang

  • 初級會員
  • **
  • 文章數: 23
    • 檢視個人資料
C.喵喵抓老鼠
« 於: 三月 09, 2010, 10:36:10 pm »

代碼: [選擇]
**********************************************************************************/
/*  Problem: b224 "C. " from 2008 NPSC 國中組決賽             */
/*  Language: C++                                                                 */
/*  Result: AC (8ms, 822KB) on ZeroJudge                                          */
/*  Author: wudaiyang at 2010-03-09 22:25:49                                      */
/**********************************************************************************/


#include<iostream>
#include <string>
#include<cstdio>
int x[10000],y[10000];
short int b[101][101];
using namespace std;
int main(){string s;int n,i;char c;
while(cin>>n && n!=0){int xhead=0,yhead=0,xtail=0,ytail=0;
for(i=1;i<=n;i++){
cin>>s;s='#'+s;
for(int j=1;j<=s.length();j++){c=s[j];
if (c=='#'){b[i][j]=1;}
else if(c=='K'){x[xhead++]=i;y[yhead++]=j;}
else if (c=='.'){b[i][j]=0;}
else b[i][j]=2;}
}
int w=0,p,xi,yi;
while(xhead!=xtail){++w;p=xhead-xtail;
for(i=1;i<=p;i++){xi=x[xtail++];yi=y[ytail++];
if(b[xi][yi+1]==2){cout<<w<<endl;goto end;}
else if(b[xi][yi+1]==0){x[xhead++]=xi;y[yhead++]=yi+1;b[xi][yi+1]=1;}

if(b[xi][yi-1]==2){cout<<w<<endl;goto end;}
else if(b[xi][yi-1]==0){x[xhead++]=xi;y[yhead++]=yi-1;b[xi][yi-1]=1;}

if(b[xi+1][yi]==2){cout<<w<<endl;goto end;}
else if(b[xi+1][yi]==0){x[xhead++]=xi+1;y[yhead++]=yi;b[xi+1][yi]=1;}

if(b[xi-1][yi]==2){cout<<w<<endl;goto end;}
else if(b[xi-1][yi]==0){x[xhead++]=xi-1;y[yhead++]=yi;b[xi-1][yi]=1;}
}

}
cout<<"= =\""<<endl;
end:{}
}

 return 0;
}
這是我自己陣列實做佇列不用內建
可惡我小國中ㄉ時候怎麼......
« 上次編輯: 十二月 26, 2011, 10:57:26 am 由 sagit »
記錄

Nineguan

  • 初級會員
  • **
  • 文章數: 43
    • 檢視個人資料
回覆: 喵喵抓老鼠
« 回覆 #1 於: 三月 13, 2010, 09:38:04 am »

這是陣列實作吧
記錄

skipper

  • 初級會員
  • **
  • 文章數: 28
    • 檢視個人資料
Re: C.喵喵抓老鼠
« 回覆 #2 於: 十一月 03, 2013, 09:20:16 am »

代碼: [選擇]
#include <iostream>
#include <string>
#include <map>
#include <queue>
using namespace std;
int grid[100][100],N,M;
map<char,int> tr;
enum {WALL=-3,MOUSE,SPACE,CAT};
struct Position {int r; int c;};
Position k;

queue<Position> q;
Position moves[4]={{0,1},{1,0},{0,-1},{-1,0}};
bool FOUND;
int steps;
int main(){
tr['#']=WALL, tr['@']=MOUSE, tr['.']=SPACE, tr['K']=CAT;
while(cin>>N && N>0){
for (int i=0;i<N;i++){
string row; cin >> row;
M = row.length();
for (int j=0;j<M;j++){
grid[i][j]=tr[row[j]];
if (row[j]=='K') {k.r=i; k.c=j;};
}
}
FOUND = false;
while(!q.empty()) q.pop();
q.push(k);
while(!q.empty()&&(!FOUND)){
k=q.front();q.pop();
steps = grid[k.r][k.c]+1;
for (int i=0;i<4 &&(!FOUND);i++){
Position p = {k.r+moves[i].r, k.c+moves[i].c};
switch(grid[p.r][p.c]){
case MOUSE:
FOUND=true;
break;
case SPACE:
grid[p.r][p.c]=steps;
q.push(p);
}
}
}
if(FOUND)
cout << steps << endl;
else
cout << "= =\"" << endl;
}
}
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2008國中組決賽
 C.喵喵抓老鼠