Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct trip
- {
- bool bol;
- short int x,y;
- };
- trip dp[300][300][300]={1};
- int main()
- {
- short int w,h;
- short int n;
- ios::sync_with_stdio(0);
- cin>>w>>h;
- cin>>n;
- short int x1,x2,y1,y2;
- cin>>x1>>y1>>x2>>y2;
- for(short int i=x1-1;i<x2;i++){
- for(short int j=y1-1;j<y2;j++){
- if(i>x2 || i<x1 || j>y2 || j<y1)dp[i][j][0].bol=1;
- else dp[i][j][0].bol=0;
- }
- }
- for(int k=1;k<n;k++){
- cin>>x1>>y1>>x2>>y2;
- for(short int i=0;i<w;i++){
- for(int j=0;j<h;j++){
- if(i>0 && dp[i-1][j][k-1].bol && (i>x2 || i<x1 || j>y2 || j<y1)){
- dp[i][j][k].bol=1;
- dp[i][j][k].x=i-1;
- dp[i][j][k].y=j;
- }
- else if(i<w-1 && dp[i+1][j][k-1].bol && (i>x2 || i<x1 || j>y2 || j<y1)){
- dp[i][j][k].bol=1;
- dp[i][j][k].x=i+1;
- dp[i][j][k].y=j;
- }
- else if(j<h-1 && dp[i][j+1][k-1].bol && (i>x2 || i<x1 || j>y2 || j<y1)){
- dp[i][j][k].bol=1;
- dp[i][j][k].x=i;
- dp[i][j][k].y=j+1;
- }
- else if(j>0 && dp[i][j-1][k-1].bol && (i>x2 || i<x1 || j>y2 || j<y1)){
- dp[i][j][k].bol=1;
- dp[i][j][k].x=i;
- dp[i][j][k].y=j-1;
- }
- else dp[i][j][k].bol=0;
- }
- }
- }
- stack<trip> ans;
- for(int i=0;i<w;i++){
- for(int j=0;j<h;j++){
- if(dp[i][j][n-1].bol){
- short int k=n-1;
- while(k>-1){
- ans.push(dp[i][j][k]);
- short int f,g;
- f=dp[i][j][k].x;
- g=dp[i][j][k].y;
- i=f;
- j=g;
- k--;
- }
- while(!ans.empty()){
- cout<<ans.top().x+1<<" "<<ans.top().y+1<<endl;
- ans.pop();
- }
- return 0;
- }
- }
- }
- cout<<"Impossible";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement