Advertisement
Guest User

Untitled

a guest
Apr 24th, 2017
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6.  
  7. struct trip
  8. {
  9. bool bol;
  10. short int x,y;
  11. };
  12.  
  13. trip dp[300][300][300]={1};
  14.  
  15. int main()
  16. {
  17. short int w,h;
  18. short int n;
  19. ios::sync_with_stdio(0);
  20. cin>>w>>h;
  21. cin>>n;
  22. short int x1,x2,y1,y2;
  23. cin>>x1>>y1>>x2>>y2;
  24. for(short int i=x1-1;i<x2;i++){
  25. for(short int j=y1-1;j<y2;j++){
  26. if(i>x2 || i<x1 || j>y2 || j<y1)dp[i][j][0].bol=1;
  27. else dp[i][j][0].bol=0;
  28. }
  29. }
  30. for(int k=1;k<n;k++){
  31. cin>>x1>>y1>>x2>>y2;
  32. for(short int i=0;i<w;i++){
  33. for(int j=0;j<h;j++){
  34. if(i>0 && dp[i-1][j][k-1].bol && (i>x2 || i<x1 || j>y2 || j<y1)){
  35. dp[i][j][k].bol=1;
  36. dp[i][j][k].x=i-1;
  37. dp[i][j][k].y=j;
  38. }
  39. else if(i<w-1 && dp[i+1][j][k-1].bol && (i>x2 || i<x1 || j>y2 || j<y1)){
  40. dp[i][j][k].bol=1;
  41. dp[i][j][k].x=i+1;
  42. dp[i][j][k].y=j;
  43. }
  44. else if(j<h-1 && dp[i][j+1][k-1].bol && (i>x2 || i<x1 || j>y2 || j<y1)){
  45. dp[i][j][k].bol=1;
  46. dp[i][j][k].x=i;
  47. dp[i][j][k].y=j+1;
  48. }
  49. else if(j>0 && dp[i][j-1][k-1].bol && (i>x2 || i<x1 || j>y2 || j<y1)){
  50. dp[i][j][k].bol=1;
  51. dp[i][j][k].x=i;
  52. dp[i][j][k].y=j-1;
  53. }
  54. else dp[i][j][k].bol=0;
  55. }
  56. }
  57. }
  58. stack<trip> ans;
  59. for(int i=0;i<w;i++){
  60. for(int j=0;j<h;j++){
  61. if(dp[i][j][n-1].bol){
  62. short int k=n-1;
  63. while(k>-1){
  64. ans.push(dp[i][j][k]);
  65. short int f,g;
  66. f=dp[i][j][k].x;
  67. g=dp[i][j][k].y;
  68. i=f;
  69. j=g;
  70. k--;
  71. }
  72. while(!ans.empty()){
  73. cout<<ans.top().x+1<<" "<<ans.top().y+1<<endl;
  74. ans.pop();
  75. }
  76. return 0;
  77. }
  78. }
  79. }
  80. cout<<"Impossible";
  81. return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement