题解 CF48E 【Ivan the Fool VS Gorynych the Dragon】
eduarte
2019-05-17 23:03:55
**思路:**
由于数据量很小，所以直接使用广度优先+动态规划解是否能打败龙
如果无法打败则再用深度优先搜索判断一下有无环路即可
**代码:**
```cpp
/*
http://codeforces.com/problemset/problem/48/E
Ivan the Fool VS Gorynych the Dragon
*/
#include <bits/stdc++.h>
using namespace std;
int h,t,r,n,m;
int times = 1,max_dis = -1;
int graph[512][512],vis[512][512];
queue <int> task;
queue <int> empty;
struct tasks{
int head,tail;
}tasks[5120000];
struct head{
int head,tail;
}head[256];
struct tail{
int head,tail;
}tail[256];
void dp(){
int x,y;
while(!task.empty()){
x = tasks[task.front()].head;
y = tasks[task.front()].tail;
task.pop();
for(int i = 1;i<=n;i++){
if(i>x){
break;
}
if(~graph[0][0]){
return;
}
if(graph[x+head[i].head][y+head[i].tail]==-1||graph[x+head[i].head][y+head[i].tail]>graph[x][y]+1){
graph[x+head[i].head][y+head[i].tail] = graph[x][y]+1;
if(x+head[i].head+y+head[i].tail<=r){
task.push(times);
tasks[times].head = x+head[i].head;
tasks[times].tail = y+head[i].tail;
times++;
}
else{
max_dis = max(max_dis,graph[x+head[i].head][y+head[i].tail]);
}
}
}
for(int i = 1;i<=m;i++){
if(i>y){
break;
}
if(~graph[0][0]){
return;
}
if(graph[x+tail[i].head][y+tail[i].tail]==-1||graph[x+tail[i].head][y+tail[i].tail]>graph[x][y]+1){
graph[x+tail[i].head][y+tail[i].tail] = graph[x][y]+1;
if(x+tail[i].head+y+tail[i].tail<=r){
task.push(times);
tasks[times].head = x+tail[i].head;
tasks[times].tail = y+tail[i].tail;
times++;
}
else{
max_dis = max(max_dis,graph[x+tail[i].head][y+tail[i].tail]);
}
}
}
}
return;
}
void find_max(){
memset(graph,-1,sizeof(graph));
graph[h][t] = 0;
int x,y;
while(!task.empty()){
x = tasks[task.front()].head;
y = tasks[task.front()].tail;
task.pop();
for(int i = 1;i<=n;i++){
if(i>x){
break;
}
if(graph[x+head[i].head][y+head[i].tail]<graph[x][y]+1){
graph[x+head[i].head][y+head[i].tail] = graph[x][y]+1;
if(x+head[i].head+y+head[i].tail<=r){
task.push(times);
tasks[times].head = x+head[i].head;
tasks[times].tail = y+head[i].tail;
times++;
}
else{
max_dis = max(max_dis,graph[x+head[i].head][y+head[i].tail]);
}
}
}
for(int i = 1;i<=m;i++){
if(i>y){
break;
}
if(graph[x+tail[i].head][y+tail[i].tail]<graph[x][y]+1){
graph[x+tail[i].head][y+tail[i].tail] = graph[x][y]+1;
if(x+tail[i].head+y+tail[i].tail<=r){
task.push(times);
tasks[times].head = x+tail[i].head;
tasks[times].tail = y+tail[i].tail;
times++;
}
else{
max_dis = max(max_dis,graph[x+tail[i].head][y+tail[i].tail]);
}
}
}
}
return;
}
bool find_annulus(int x,int y){
vis[x][y]=2;
for(int i=1;i<=n&&i<=x;i++){
int xx=x+head[i].head,yy=y+head[i].tail;
if(xx+yy>r)continue;
if(!vis[xx][yy]){
if(find_annulus(xx,yy))return true;
}
else if(vis[xx][yy]==2)return true;
}
for(int i=1;i<=m&&i<=y;i++){
int xx=x+tail[i].head,yy=y+tail[i].tail;
if(xx+yy>r)continue;
if(!vis[xx][yy]){
if(find_annulus(xx,yy))return true;
}
else if(vis[xx][yy]==2)return true;
}
vis[x][y]=1;
return false;
}
void is_ivan_die(){
if(find_annulus(h,t)){
cout<<"Draw";
}
else{
graph[h][t] = 0;
task.push(0);
find_max();
cout<<"Zmey"<<endl<<max_dis;
}
return;
}
int main(){cin>>h>>t>>r;
cin>>n;
for(int i = 1;i<=n;i++){
cin>>head[i].head>>head[i].tail;
head[i].head = head[i].head-i;
}
cin>>m;
for(int i = 1;i<=m;i++){
cin>>tail[i].head>>tail[i].tail;
tail[i].tail = tail[i].tail-i;
}
memset(graph,-1,sizeof(graph));
graph[h][t] = 0;
task.push(0);
tasks[0].head = h;
tasks[0].tail = t;
dp();
if(graph[0][0]!=-1){
cout<<"Ivan"<<endl<<graph[0][0];
}
else{
is_ivan_die();
}
cout<<endl;
return 0;
}
```