單詞方陣 - 洛谷

思路：在字符方陣中找到y并將其坐標存入數組，再找其八個方向是否有目標字符，有的話就深搜一個方向，能搜完就將數組標記，最好標記的就輸入字符，沒標記的就輸出*。

代碼如下：

#include<stdio.h>
int next1[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
char s[8]={'y','i','z','h','o','n','g'},s1[110][110];
int sx[1111111],sy[1111111],book[111][111];
int dfs(int x,int y,int n,int m)
{m++;if(m>=7){return 1;}int tx1,ty1;tx1=x+next1[n][0];ty1=y+next1[n][1];if(s1[tx1][ty1]==s[m]){book[tx1][ty1]+=dfs(tx1,ty1,n,m);return book[tx1][ty1];}return 0;
}
int main()
{int t,k=1;scanf("%d",&t);for(int i=1;i<=t;i++){scanf("%s",s1[i]);}for(int i=1;i<=t;i++){for(int j=0;j<t;j++){if(s1[i][j]==s[0]){sx[k]=i;sy[k]=j;k++;}}}for(int i=1;i<k;i++){for(int j=0;j<8;j++){int tx=sx[i]+next1[j][0];int ty=sy[i]+next1[j][1];if(s1[tx][ty]==s[1]){book[tx][ty]+=dfs(tx,ty,j,1);book[sx[i]][sy[i]]+=dfs(tx,ty,j,1);}}}for(int i=1;i<=t;i++){for(int j=0;j<t;j++){if(book[i][j]>=1)printf("%c",s1[i][j]);elseprintf("*");}printf("\n");}return 0;
}

[USACO08FEB] Meteor Shower S - 洛谷

思路：先初始化地圖time數組為10000，然后輸入坐標和爆炸時間，判斷此點以及周圍4個點的爆炸時間會不會小于原本的時間，小于則更新此點地圖time數組，標記初始點，找點，如果有一個點數值為10000，那么這就是安全的，輸出這一點時間即可，如果最后點都用完了還沒找到就輸出-1.

代碼如下：

#include<stdio.h>
#include<queue>
using namespace std;
int next1[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int time[305][305],book[305][305];
queue<int>q1,q2,time1;
int main()
{for(int i=0;i<=302;i++){for(int j=0;j<=302;j++){time[i][j]=10000;}}int n;scanf("%d",&n);for(int i=0;i<n;i++){int a,s,time3;scanf("%d%d%d",&a,&s,&time3);if(time[a][s]>time3)time[a][s]=time3;for(int j=0;j<4;j++){int x,y;x=a+next1[j][0];y=s+next1[j][1];if(x>=0&&y>=0&&time3<time[x][y]){time[x][y]=time3;}}}q1.push(0);q2.push(0);time1.push(0);book[0][0]=1;while(!q1.empty()){int nx=q1.front();int ny=q2.front();int st=time1.front()+1;if(time[nx][ny]==10000){printf("%d",st-1);return 0;}if(time[nx][ny]<=st-1){q1.pop();q2.pop();time1.pop();}for(int j=0;j<4;j++){int tx,ty;;tx=nx+next1[j][0];ty=ny+next1[j][1];if(tx>=0&&ty>=0&&book[tx][ty]==0&&time[tx][ty]>st){q1.push(tx);q2.push(ty);time1.push(st);book[tx][ty]=1;}}q1.pop();q2.pop();time1.pop();}printf("-1");return 0;
}