Plague Inc

　

plague inc

题目：

plague inc. is a famous game, which player develop virus to ruin the world.

JSZKC wants to model this game. Let's consider the world has N\times MN×M cities. The world has NN rows and MM columns. The city in the XX row and the YY column has coordinate (X,Y)(X,Y).

There are KK cities which are sources of infection at the 0^{th}0th day. Each day the infection in any infected city will spread to the near four cities (if exist).

JSZKC wants to know which city is the last one to be infected. If there are more than one cities , answer the one with smallest XX firstly, smallest YY secondly.

Input Format

The input file contains several test cases, each of them as described below.

• The first line of the input contains two integers NN and MM (1 \le N,M \le 2000)(1≤N,M≤2000), giving the number of rows and columns of the world.
• The second line of the input contain the integer KK (1 \le K \le 10)(1≤K≤10).
• Then KK lines follow. Each line contains two integers X_iXi​ and Y_iYi​, indicating (X_i,Y_i)(Xi​,Yi​) is a source. It's guaranteed that the coordinates are all different.

There are no more than 2020 test cases.

Output Format

For each testcase, output one line with coordinate XX and YY separated by a space.

样例输入

3 3
1
2 2
3 3
2
1 1
3 3

样例输出

1 1
1 3

题目来源

The 2018 ACM-ICPC China JiangSu Provincial Programming Contest

分析：

很显然的广搜问题，最后入队的点就是最后一个感染的点；

代码：

#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
struct node
{
    int xx;
    int yy;
    int step;
}head,tail,maxx;
queue<node>q;
int nextt[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int mAPP[2005][2005];
bool book[2005][2005];
int n,m,k,xxx,yyy;
bool charge(int a,int b)
{
    if(a<=0||b<=0||a>n||b>m||(book[a][b]==1))
        return 0;
    else
        return 1;
}
int main()
{
    int i,j,tx,ty;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(book,0,sizeof(book));
        scanf("%d",&k);
        for(i=0;i<k;i++)
        {
            scanf("%d %d",&xxx,&yyy);
            head.xx=xxx;
            head.yy=yyy;
            head.step=0;
            q.push(head);
            book[xxx][yyy]=1;
        }
        if(k==m*n)
        {
            printf("1 1\n");
            continue;
        }
        maxx.step=-1;
        while(!q.empty())
        {
            head=q.front();
            q.pop();
            for(i=0;i<4;i++)
            {
                tx=head.xx+nextt[i][0];
                ty=head.yy+nextt[i][1];
                if(charge(tx,ty))
                {
                    book[tx][ty]=1;
                    tail.xx=tx;
                    tail.yy=ty;
                    tail.step=head.step+1;
                   /* if(tail.step>maxx.step)
                    {
                        maxx.xx=tx;
                        maxx.yy=ty;
                        maxx.step=tail.step;
                    }
                    else if(tail.step==maxx.step)
                    {
                        if(tx<maxx.xx)
                        {
                            maxx.xx=tx;
                            maxx.yy=ty;
                            maxx.step=tail.step;
                        }
                        else if(tx==maxx.xx&&ty<maxx.yy)
                        {
                            maxx.xx=tx;
                            maxx.yy=ty;
                            maxx.step=tail.step;
                        }
                    }*/
                    if(tail.step==maxx.step)
                    {
                        if(tx==maxx.xx&&ty<maxx.yy)
                        {
                            maxx.xx=tx;
                            maxx.yy=ty;
                        }
                        if(tx<maxx.xx)
                        {
                            maxx.xx=tx;
                            maxx.yy=ty;
                        }
                    }
                    if(tail.step>maxx.step)
                    {
                        maxx.xx=tx;
                        maxx.yy=ty;
                        maxx.step=tail.step;
                    }
                    q.push(tail);
                    //printf("%d %d\n",maxx.xx,maxx.yy);
                }
            }
        }
        printf("%d %d\n",maxx.xx,maxx.yy);
    }
    return 0;
}

相关阅读

Visual Studio2017自动生成的#include“stdafx.h”详

问题描述：在高版本的Visual Studio的默认设置中，会出现这么一个现象，在新建项目之后，项目会自动生成#include“stdafx.h”的头文件，而

sql distinct

---沒有去除重復的記錄 select distinct ContractLaborEmployeeUidKey,ContractLaborEndDate from ContractLaborList order by C

php include_once加载其他文件后无法找到里面的方法

php中引入其他文件需要使用include及相关函数include_once($_SERVER['DOCUMENT_ROOT'].'/xxxx/UrlTools.php'); 但要使用里面的

davinc架构--环境搭建篇 【转】

Davinci架构有硬件环境和软件环境：硬件环境就不用说，肯定拥有就是支持davinci架构的芯片的开发板，我用的devkit8000，官网把它叫做DVEV

如何评价GAN网络的好坏？IS（inception score）和FID（Fréche

值得一看，总结了IS和FID的历史发展原文地址在对抗生成网络中，判别器和生成器的目标函数通常都是用来衡量它们各自做的怎么样的。例