当前位置: 代码迷 >> 综合 >> UVALive 7511 Multiplication Table
  详细解决方案

UVALive 7511 Multiplication Table

热度:63   发布时间:2024-01-10 18:46:31.0

   思路:要是没有有效元素,则是yes,若只有一个,判断他的坐标是否符合在表格中的位置,两个两个以上,则用第一个元素与其他元素作比较判断它们的相对位置符不符合表格中 的位置。

#include<bits/stdc++.h>
#define MAX 1000
using namespace std;
struct node
{int x;int y;int v;
}arr[MAX*MAX +5];
int x,y,sum;
bool work()
{for(int i=1;i*i<=arr[1].v;i++){int flag=1;if(arr[1].v%i==0){if(i>=arr[1].x&&arr[1].v/i>=arr[1].y){for(int j=2;j<=sum;j++){if((i+arr[j].x-arr[1].x)*(arr[1].v/i+arr[j].y-arr[1].y)!=arr[j].v){flag=0;}if(!flag)break;}if(flag)return true;}if(arr[1].v/i>=arr[1].x&&i>=arr[1].y){flag=1;for(int j=2;j<=sum;j++){if((arr[1].v/i+arr[j].x-arr[1].x)*(i+arr[j].y-arr[1].y)!=arr[j].v){flag=0;}if(!flag)break;}if(flag)return true;}}}return false;
}
int main()
{int t,now,case1=1;cin>>t;string str;while(t--){cin>>x>>y;sum=0;for(int i=1;i<=x;i++){for(int j=1;j<=y;j++){cin>>str;if(str!="?"){now=0;for(int k=0;k<str.size();k++){now=now*10+str[k]-'0';}arr[++sum].x=i;arr[sum].y=j;arr[sum].v=now;}}}printf("Case #%d: ",case1++);if(!sum){cout<<"Yes"<<endl;}else if(sum==1){int flag=0;for(int i=1;i<=sqrt(arr[1].v);i++){if(arr[1].v%i==0){if(i>=arr[1].x&&arr[1].v/i>=arr[1].y){flag=1;}else if(i>=arr[1].y&&arr[1].v/i>=arr[1].x){flag=1;}}}if(flag)cout<<"Yes"<<endl;elsecout<<"No"<<endl;}else{if(work()){cout<<"Yes"<<endl;}elsecout<<"No"<<endl;}}return 0;
}


  相关解决方案