牛客网2018年东北农业大学春季校赛（BD）

【链接】

https://www.nowcoder.com/acm/contest/93#question

【分析】

一开始直接开始敲代码了果然超时了哭哭。仔细观察，头尾结合为中间的两倍。

以5为例，（5*5/2+1）为中心数13（我就是随便叫叫），答案为13*（1+3+5+3+1）=13*13.

有了答案为中心数平方的猜想，但是我们不能胡来嘛。个数推导一下为（1+n）/2*(1+n)/2*2-n=(n*n+1)/2.

因为n为奇数嘛，所以二者相等就可以直接写啦。短的一批，这就很有灵性。

【代码】

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        long long mid=n*n/2+1;
        cout<<mid*mid<<endl;
    }
    return 0;
}

【分析】

没什么好分析的就是dfs

【代码】

#include<bits/stdc++.h>
using namespace std;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
char c[505][505];
int visit[505][505];
int n,m,re;
void dfs(int x,int y)
{
    visit[x][y]=1;
    if(c[x][y]=='t'){
        re=1;
        return;
    }
    for(int i=0;i<4;i++){
        int x1=x+dx[i];
        int y1=y+dy[i];
        if(x1>=0&&y1>=0&&x1<n&&y1<m&&visit[x1][y1]==0&&c[x1][y1]!='x')
            dfs(x1,y1);
    }
}
int main()
{
    int t,i,j;
    cin>>t;
    while(t--){
        cin>>n>>m;
        memset(c,'\0',sizeof(c));
        memset(visit,0,sizeof(visit));
        re=0;
        for(i=0;i<n;i++){
            getchar();
            scanf("%s",c[i]);
        }
        int p,q;
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
                if(c[i][j]=='s'){
                    p=i;
                    q=j;
                    break;
                }
        dfs(p,q);
        if(re==1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}